oj.uz

Submission #1003365

# Submission time Handle Problem Language Result Execution time Memory
1003365 2024-06-20T09:16:51 Z vjudge1 Flooding Wall (BOI24_wall) C++17
0 / 100
 5000 ms 10248 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 3408 ms 796 KB Output is correct
11 Correct 3398 ms 812 KB Output is correct
12 Correct 3373 ms 776 KB Output is correct
13 Correct 3259 ms 936 KB Output is correct
14 Execution timed out 5055 ms 10248 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -