From c394b027f6bc7ae61ee88e2cad3ccc692472caa6 Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Sat, 26 Mar 2022 21:33:04 -0500 Subject: 21.5 jan gold drought --- 21.5/jan/gold/drought.cpp | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) create mode 100644 21.5/jan/gold/drought.cpp 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 +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +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; +} -- cgit v1.2.3-70-g09d2