Submission #1342819

#TimeUsernameProblemLanguageResultExecution timeMemory
1342819ramzialoulouFlooding Wall (BOI24_wall)C++20
48 / 100
494 ms1114112 KiB
#include <bits/stdc++.h>
 
using namespace std;

const int md = int(1e9) + 7;

int mul(int a, int b) {
  long long m = 1LL * a * b;
  return m % md;
}

void add(int& a, int b) {
  a += b;
  if (a >= md) a -= md;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  vector<int> b(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  const int MX = max(*max_element(a.begin(), a.end()), *max_element(b.begin(), b.end())) + 1;
  vector dpL(n + 1, vector<int>(MX));
  dpL[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int h = 0; h < MX; h++) {
      add(dpL[i + 1][max(h, a[i + 1])], dpL[i][h]);
      add(dpL[i + 1][max(h, b[i + 1])], dpL[i][h]);
    }
  }
  vector dpR(n + 2, vector<int>(MX));
  dpR[n + 1][0] = 1;
  for (int i = n + 1; i >= 1; i--) {
    for (int h = 0; h < MX; h++) {
      add(dpR[i - 1][max(h, a[i - 1])], dpR[i][h]);
      add(dpR[i - 1][max(h, b[i - 1])], dpR[i][h]);
    }
  }
  vector pre(n + 1, vector<int>(MX + 1));
  for (int i = 1; i <= n; i++) {
    for (int h = MX - 1; h >= 1; h--) {
      add(pre[i][h], pre[i][h + 1]);
      add(pre[i][h], dpL[i][h]);
    }
  }
  vector suf(n + 1, vector<int>(MX + 1));
  for (int i = n; i >= 1; i--) {
    for (int h = MX - 1; h >= 1; h--) {
      add(suf[i][h], suf[i][h + 1]);
      add(suf[i][h], dpR[i][h]);
    }
  }
  int ans = 0;
  for (int i = 2; i < n; i++) {
    for (int x : {a[i], b[i]}) {
      for (int h = x + 1; h < MX; h++) {
        int gL = pre[i - 1][h + 1];
        int gR = suf[i + 1][h + 1];
        int L = dpL[i - 1][h];
        int R = dpR[i + 1][h];
        int d = h - x;
        add(ans, mul(d, mul(L, gR)));
        add(ans, mul(d, mul(R, gL)));
        add(ans, mul(d, mul(L, R)));
      }
    }
  }
  cout << ans << '\n';
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...