Submission #1003365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003365		vjudge1	Flooding Wall (BOI24_wall)	C++17	0 / 100	5055 ms	10248 KiB

Main

#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";
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 19
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30