Submission #1003365

#TimeUsernameProblemLanguageResultExecution timeMemory
1003365vjudge1Flooding Wall (BOI24_wall)C++17
0 / 100
5055 ms10248 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()

const int N = 5e5+5, mod = 1e9+7;

int n, a[N], b[N], dp[2][N];

int pw(int x, int y) {
  return (!y ? 1 : pw(x*x % mod, y/2) * (y%2 ? x : 1) % mod);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    if (a[i] > b[i]) swap(a[i], b[i]);
  }

  // dp[i][j] = suma de agua que consigo con los primeros j muros donde el j-esimo vale (i == 0 ? a[j] : b[j])
  dp[0][0] = dp[1][0] = 0;

  for (int j = 1; j < n; j++) {
    // i = 0
    dp[0][j] = 0;

    int w = 1;
    int sum1 = 0;
    int sum2 = 0;
    for (int k = j-1; k >= 0; k--) {
      int sum = (sum1*w % mod + sum2*w % mod * pw(2, mod-2) % mod) % mod;

      if (a[k] >= a[j] || !k) {
        dp[0][j] += ((w * min(a[j], a[k]) % mod * (j-k-1) % mod - sum + mod) % mod * pw(2, k) % mod + dp[0][k]) % mod;
        dp[0][j] %= mod;
      }

      if (b[k] >= a[j] || !k) {
        dp[0][j] += ((w * min(a[j], b[k]) % mod * (j-k-1) % mod - sum + mod) % mod * pw(2, k) % mod + dp[1][k]) % mod;
        dp[0][j] %= mod;
      }

      if (b[k] < a[j]) {
        w *= 2;
        w %= mod;

        sum2 += (a[k] + b[k]) % mod;
        sum2 %= mod;
      }
      else if (a[k] < a[j]) {
        sum1 += a[k];
        sum1 %= mod;
      }

      if (a[k] >= a[j]) break;
    }

    // i = 1
    dp[1][j] = 0;

    w = 1;
    sum1 = 0;
    sum2 = 0;
    for (int k = j-1; k >= 0; k--) {
      int sum = sum1*w + sum2*w / 2;
      
      if (a[k] >= b[j] || !k) {
        dp[1][j] += ((w * min(b[j], a[k]) % mod * (j-k-1) % mod - sum + mod) % mod * pw(2, k) % mod + dp[0][k]) % mod;
        dp[1][j] %= mod;
      }

      if (b[k] >= b[j] || !k) {
        dp[1][j] += ((w * min(b[j], b[k]) % mod * (j-k-1) % mod - sum + mod) % mod * pw(2, k) % mod + dp[1][k]) % mod;
        dp[1][j] %= mod;
      }

      if (b[k] < b[j]) {
        w <<= 1;
        w %= mod;

        sum2 += (a[k] + b[k]) % mod;
        sum2 %= mod;
      }
      else if (a[k] < b[j]) {
        sum1 += a[k];
        sum1 %= mod;
      }

      if (a[k] >= b[j]) break;
    }
  }

/*
  for (int i = 0; i < n; i++) {
    cerr << dp[0][i] << " " << dp[1][i] << endl;
  }
  */

  cout << (dp[0][n-1] + dp[1][n-1]) % mod << "\n";
}
#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...