Submission #1237927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237927		asdfgrace	Flooding Wall (BOI24_wall)	C++20	12 / 100	36 ms	12104 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
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> dp(n, 0), ways(n, 0);
  ways[0] = 1;
  ways[1] = 2;
  long long dp_pref = 0, ways_pref = 1, ways_sum = 1;
  for (int i = 2; i < n; i++) {
    pv(i); pv(ways_sum);
    dp[i] = (dp_pref + ways_sum) % mod;
    dp[i] += dp[i - 1]; dp[i] %= mod;
    ways[i] = (ways[i - 1] * 2) % mod;
    dp_pref += dp[i - 1]; dp_pref %= mod;
    ways_pref += ways[i - 1]; ways_pref %= mod;
    ways_sum += ways_pref; ways_sum %= mod;
  }
  parr(ways); parr(dp);
  dp_pref += dp[n - 1]; dp_pref %= mod;
  cout << dp_pref << '\n';
}

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