Submission #1155711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155711		adiyer	Flooding Wall (BOI24_wall)	C++20	36 / 100	414 ms	158896 KiB

Main

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define len(s) (ll) s.size()
#define pb push_back
#define F first 
#define S second 

using namespace std;

typedef long long ll;

const int N = 1e4 + 3; 
const int MAX = 1e3 + 11;
const int P = 31;
const int mod = 1e9 + 7;
const ll inf = 1e18;

ll n, res;
ll a[N], b[N], dp[N][MAX][2], p[MAX], s[MAX];

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  for(ll i = 1; i <= n; i++) cin >> a[i];
  for(ll i = 1; i <= n; i++) cin >> b[i];
  for(ll fg = 0; fg < 2; fg++){
    if(fg){
      reverse(a + 1, a + n + 1);
      reverse(b + 1, b + n + 1);
    }
    dp[0][0][fg] = 1;
    for(ll x = 0; x <= 1000; x++) p[x] = 1;
    for(ll i = 1; i <= n; i++){
      for(ll x = 1000; x >= 0; x--){
        ll &y = dp[i][x][fg];
        if(a[i] > x && b[i] > x) y = 0;
        else if(a[i] > x || b[i] > x){
          if(a[i] == x || b[i] == x) y = p[x];
          else y = dp[i - 1][x][fg];
        }
        else{
          if(a[i] == x && b[i] == x) y = p[x] * 2;
          else if(a[i] == x || b[i] == x) y = p[x] + dp[i - 1][x][fg];
          else y = dp[i - 1][x][fg] * 2;
        }
        y %= mod;
      }
      for(ll x = 0; x <= 1000; x++){
        if(x) p[x] = (p[x - 1] + dp[i][x][fg]) % mod;
        else p[x] = dp[i][x][fg];
      }
    }
    if(fg){
      reverse(a + 1, a + n + 1);
      reverse(b + 1, b + n + 1);
    }
  }
  for(ll i = 2; i < n; i++){
    ll l = i - 1, r = n - i, cur1 = 0, cur2 = 0;
    for(ll x = 1000; x >= 0; x--){
      s[x] = s[x + 1] + dp[r][x][1];
    }
    for(ll x = 0; x <= 1000; x++){ 
      res += (dp[l][x][0] * cur1) % mod, res %= mod;
      res += (dp[l][x][0] * cur2) % mod, res %= mod;
      if(x > a[i]) 
        res += ((dp[l][x][0] * s[x]) % mod * (x - a[i])) % mod, res %= mod, 
        cur1 += (dp[r][x][1] * (x - a[i])) % mod, cur1 %= mod;
      if(x > b[i]) 
        res += ((dp[l][x][0] * s[x]) % mod * (x - b[i])) % mod, res %= mod,
        cur2 += (dp[r][x][1] * (x - b[i])) % mod, cur2 %= mod;
    }
  }
  cout << res;
}

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