Submission #1342903

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

const int md = int(1e9) + 7;
const int N = int(1e4) + 9;
int a[N];
int b[N];
int idx[2][N];
int dpL[N][N];
int dpR[N][N];
int pre[N][N];
int suf[N][N];

int mul(int a, int b) {
  return 1LL * a * b % 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> c;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    c.push_back(a[i]);
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
    c.push_back(b[i]);
  }
  c.push_back(0);
  sort(c.begin(), c.end());
  c.erase(unique(c.begin(), c.end()), c.end());
  int m = int(c.size());
  for (int i = 1; i <= n; i++) {
    idx[0][i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin();
    idx[1][i] = lower_bound(c.begin(), c.end(), b[i]) - c.begin();
  }
  dpL[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      int ka = (c[j] > a[i + 1] ? j : idx[0][i + 1]);
      int kb = (c[j] > b[i + 1] ? j : idx[1][i + 1]);
      add(dpL[i + 1][ka], dpL[i][j]);
      add(dpL[i + 1][kb], dpL[i][j]);
    }
  }
  dpR[n + 1][0] = 1;
  for (int i = n + 1; i >= 1; i--) {
    for (int j = 0; j < m; j++) {
      int ka = (c[j] > a[i - 1] ? j : idx[0][i - 1]);
      int kb = (c[j] > b[i - 1] ? j : idx[1][i - 1]);
      add(dpR[i - 1][ka], dpR[i][j]);
      add(dpR[i - 1][kb], dpR[i][j]);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = m - 1; j >= 1; j--) {
      add(pre[i][j], pre[i][j + 1]);
      add(pre[i][j], dpL[i][j]);
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = m - 1; j >= 1; j--) {
      add(suf[i][j], suf[i][j + 1]);
      add(suf[i][j], dpR[i][j]);
    }
  }
  int ans = 0;
  for (int i = 2; i < n; i++) {
    for (int x : {a[i], b[i]}) {
      for (int j = 0; j < m; j++) {
        if (c[j] <= x) continue;
        int gL = pre[i - 1][j + 1];
        int gR = suf[i + 1][j + 1];
        int L = dpL[i - 1][j];
        int R = dpR[i + 1][j];
        int d = c[j] - 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...