제출 #1238016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238016		asdfgrace	Flooding Wall (BOI24_wall)	C++20	8 / 100	166 ms	436 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];
  }
  long long ans = 0;
  for (int mask = 0; mask < (1 << n); mask++) {
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
      c[i] = ((mask & (1 << i)) ? b[i] : a[i]);
    }
    int mxe = 0, ind = 0;
    for (int i = 0; i < n; i++) {
      if (c[i] > mxe) {
        mxe = c[i];
        ind = i;
      }
    }
    long long sum = 0, mx = 0;
    int prev = -1;
    for (int i = 0; i <= ind; i++) {
      if (c[i] >= mx) {
        if (i > 0) {
          ans += ((long long) (i - prev - 1) * mx - sum) % mod; ans %= mod;
        }
        mx = c[i];
        prev = i;
        sum = 0;
      } else {
        sum += c[i];
      }
    }
    sum = 0; mx = 0;
    prev = n;
    for (int i = n - 1; i >= ind; i--) {
      if (c[i] >= mx) {
        if (i < n - 1) {
          ans += ((long long) (prev - i - 1) * mx - sum) % mod; ans %= mod;
        }
        mx = c[i];
        prev = i;
        sum = 0;
      } else {
        sum += c[i];
      }
    }
  }
  cout << ans << '\n';
}

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