Submission #1238030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238030		asdfgrace	Flooding Wall (BOI24_wall)	C++20	25 / 100	5095 ms	584 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define parr(x) dbg(cerr << #x << " = "; for (auto y : x) cerr << y << ' '; cerr << '\n';)
#define parr2d(x) dbg(cerr << #x << " = \n"; for (auto _ : x) {parr(_);} cerr << '\n';)

/*
1
bitmask
2
for each pair of walls
calculate the sum of all possible sums of elements between these
such that all of them are less than a certain value
for this, doing all ranges & all values will work
so now, what if there's an even taller segment on the outside?
in addition to calculating the segment's sum, also calculate the # of
ways for things on the outside to exist such that it's not true that
there's a bigger element to the left AND the right
ways_left * smaller_right + smaller_left * ways_right
- smaller_left * smaller_right
3
4
5
let i be the end of a segment
dp[i] = the answer
ways[i] = # of ways so that h[i] = 2
for i, for all j <= i - 2
dp[i] += dp[j] + ways[j] * (i - j - 1)
ways[i] += ways[j]
*/

const long long mod = 1e9 + 7;

int main () {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }
  vector<long long> p2(n + 1);
  p2[0] = 1;
  for (int i = 1; i <= n; i++) {
    p2[i] = (p2[i - 1] * 2) % mod;
  }
  long long ans = 0;
  for (int l = n - 1; l >= 0; l--) {
    for (int r = l + 2; r < n; r++) {
      for (int lv = 0; lv < 2; lv++) {
        for (int rv = 0; rv < 2; rv++) {
          int lval = (lv == 0 ? a[l] : b[l]);
          int rval = (rv == 0 ? a[r] : b[r]);
          int x = min(lval, rval);
          long long ways = 1, in = 0;
          for (int i = l + 1; i < r; i++) {
            int new_in = 0;
            if (a[i] < x) {
              new_in = ((x - a[i]) * ways + in) % mod;
            }
            if (b[i] < x) {
              new_in += ((x - b[i]) * ways + in) % mod; new_in %= mod;
            }
            in = new_in;
            int tmp = 2;
            if (a[i] >= x) tmp--;
            if (b[i] >= x) tmp--;
            ways *= tmp; ways %= mod;
          }
          long long lw = 1, rw = 1;
          for (int i = 0; i < l; i++) {
            int tmp = 2;
            if (a[i] > lval) tmp--; if (b[i] > lval) tmp--;
            lw *= tmp; lw %= mod;
          }
          for (int i = r + 1; i < n; i++) {
            int tmp = 2;
            if (a[i] > rval) tmp--; if (b[i] > rval) tmp--;
            rw *= tmp; rw %= mod;
          }
          long long out = 1;
          if (lval > rval) {
            out = rw * p2[l] % mod;
          } else if (rval > lval) {
            out = lw * p2[n - 1 - r] % mod;
          } else {
            out = (p2[l + (n - 1 - r)] + mod -
              (((p2[l] + mod - lw) % mod)
                * ((p2[n - 1 - r] + mod - rw) % mod) % mod)) % mod;
          }
          ans += in * out % mod;
          ans %= mod;
        }
      }
    }
  }
  cout << ans << '\n';
}

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