diff options
| -rw-r--r-- | 21.5/jan/gold/drought.cpp | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/21.5/jan/gold/drought.cpp b/21.5/jan/gold/drought.cpp new file mode 100644 index 0000000..e6edda4 --- /dev/null +++ b/21.5/jan/gold/drought.cpp @@ -0,0 +1,33 @@ +#include <bits/stdc++.h> +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair<int, int>; +const int MOD = 1e9+7; + +inline int add(int a, int b) { + int c = a+b; + if (c > MOD) c -= MOD; + return c; +} + +int H[105], DP[1005]; + +int main() { + cin.tie(0)->sync_with_stdio(0); + int N; cin >> N; + for (int i = 0; i < N; ++i) cin >> H[i]; + int mn = *min_element(H, H+N), mx = *max_element(H, H+N), ans = 0; + do { + fill(DP, DP+mx+1, 1); + for (int i = 0; i < N; ++i) { + reverse(DP, DP+H[i]+1); + fill(DP+H[i]+1, DP+mx+1, 0); + partial_sum(DP, DP+mx+1, DP, add); + } + ans = add(DP[0], ans); + for (int i = 0; i < N; ++i) --H[i]; + } while (N&1 && mn-- && mx--); + cout << ans; +} |