제출 #1238108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238108		asdfgrace	Flooding Wall (BOI24_wall)	C++20	58 / 100	5094 ms	27640 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
the out can be precalculated in o(n^2)
for (i) -> this is gonna be the minimum
ok now there are still n^2 segments and 2^n arrays

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;
  }
  vector<vector<long long>> lw(2, vector<long long>(n, 1)),
    rw(2, vector<long long>(n, 1));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      long long val = (j == 0 ? a[i] : b[i]);
      for (int ii = 0; ii < i; ii++) {
        int tmp = 2;
        if (a[ii] > val) tmp--; if (b[ii] > val) tmp--;
        lw[j][i] *= tmp; lw[j][i] %= mod;
      }
      for (int ii = i + 1; ii < n; ii++) {
        int tmp = 2;
        if (a[ii] > val) tmp--; if (b[ii] > val) tmp--;
        rw[j][i] *= tmp; rw[j][i] %= mod;
      }
    }
  }
  parr2d(lw); parr2d(rw);
  long long ans = 0;
  // loop 1 - assume the left element <= right element
  for (int lv = 0; lv < 2; lv++) {
    for (int rv = 0; rv < 2; rv++) {
      for (int l = n - 1; l >= 0; l--) {
        int lval = (lv == 0 ? a[l] : b[l]);
        long long ways = 1, in = 0;
        for (int r = l + 2; r < n; r++) {
          int rval = (rv == 0 ? a[r] : b[r]);
          long long new_in = 0;
          if (a[r - 1] < lval) {
            new_in = ((lval - a[r - 1]) * ways + in) % mod;
          }
          if (b[r - 1] < lval) {
            new_in += ((lval - b[r - 1]) * ways + in) % mod; new_in %= mod;
          }
          in = new_in;
          int tmp = 2;
          if (a[r - 1] >= lval) tmp--;
          if (b[r - 1] >= lval) tmp--;
          ways *= tmp; ways %= mod;
          long long out = 1;
          if (lval > rval) {
            out = 0;
          } else if (rval > lval) {
            out = lw[lv][l] * p2[n - 1 - r] % mod;
          } else {
            out = (p2[l + (n - 1 - r)] + mod -
              (((p2[l] + mod - lw[lv][l]) % mod)
                * ((p2[n - 1 - r] + mod - rw[rv][r]) % mod) % mod)) % mod;
          }
          ans += in * out % mod;
          ans %= mod;
        }
      }
    }
  }
  // loop 2 - left > right
  for (int lv = 0; lv < 2; lv++) {
    for (int rv = 0; rv < 2; rv++) {
      for (int r = 0; r < n; r++) {
        int rval = (rv == 0 ? a[r] : b[r]);
        long long ways = 1, in = 0;
        for (int l = r - 2; l >= 0; l--) {
          int lval = (lv == 0 ? a[l] : b[l]);
          long long new_in = 0;
          if (a[l + 1] < rval) {
            new_in = ((rval - a[l + 1]) * ways + in) % mod;
          }
          if (b[l + 1] < rval) {
            new_in += ((rval - b[l + 1]) * ways + in) % mod; new_in %= mod;
          }
          in = new_in;
          int tmp = 2;
          if (a[l + 1] >= rval) tmp--;
          if (b[l + 1] >= rval) tmp--;
          ways *= tmp; ways %= mod;
          long long out = 1;
          if (lval > rval) {
            out = rw[rv][r] * p2[l] % mod;
          } else {
            out = 0;
          }
          ans += in * out % mod;
          ans %= mod;
        }
      }
    }
  }
  cout << ans << '\n';
}

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