Submission #1342996

#TimeUsernameProblemLanguageResultExecution timeMemory
1342996ramzialoulouFlooding Wall (BOI24_wall)C++20
56 / 100
5091 ms59152 KiB
#include <bits/stdc++.h>
 
using namespace std;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n + 1);
  set<int> c;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    c.insert(a[i]);
  }
  vector<int> b(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
    c.insert(b[i]);
  }
  long long ans = 0;
  vector dpL(n + 2, vector<long long>(3)), dpR = dpL;
  for (int x : c) {
    dpL[0][0] = 1;
    for (int i = 0; i < n; i++) {
      dpL[i + 1][0] = dpL[i + 1][1] = dpL[i + 1][2] = 0;
      for (int y : {a[i + 1], b[i + 1]}) {
        if (x > y) {
          dpL[i + 1][0] += dpL[i][0];
          dpL[i + 1][1] += dpL[i][1];
          dpL[i + 1][2] += dpL[i][2];
        } else if (y == x) {
          dpL[i + 1][1] += dpL[i][0] + dpL[i][1];
          dpL[i + 1][2] += dpL[i][2];
        } else {
          dpL[i + 1][2] += dpL[i][0] + dpL[i][1] + dpL[i][2];
        }
        for (int j = 0; j < 3; j++) {
          dpL[i + 1][j] %= md;
        }
      }
    }
    dpR[n + 1][0] = 1;
    for (int i = n + 1; i >= 1; i--) {
      dpR[i - 1][0] = dpR[i - 1][1] = dpR[i - 1][2] = 0;
      for (int y : {a[i - 1], b[i - 1]}) {
        if (x > y) {
          dpR[i - 1][0] += dpR[i][0];
          dpR[i - 1][1] += dpR[i][1];
          dpR[i - 1][2] += dpR[i][2];
        } else if (y == x) {
          dpR[i - 1][1] += dpR[i][0] + dpR[i][1];
          dpR[i - 1][2] += dpR[i][2];
        } else {
          dpR[i - 1][2] += dpR[i][0] + dpR[i][1] + dpR[i][2];
        }
        for (int j = 0; j < 3; j++) {
          dpR[i - 1][j] %= md;
        }
      }
    }
    for (int i = 1; i <= n; i++) {
      long long res = 0;
      res += (dpL[i - 1][1] * dpR[i + 1][1]) % md;
      res += (dpL[i - 1][2] * dpR[i + 1][1]) % md;
      res += (dpL[i - 1][1] * dpR[i + 1][2]) % md;
      ans += max(0, x - a[i]) * res % md;
      ans %= md;
      ans += max(0, x - b[i]) * res % md;
      ans %= md;
    }
  }
  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...