21.5 jan gold drought

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;
+}