Submission #1155707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155707		adiyer	Flooding Wall (BOI24_wall)	C++20	17 / 100	5099 ms	157700 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 P = 31;
const int mod = 1e9 + 7;
const ll inf = 1e18;

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

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;
    for(ll x = 0; x <= 1000; x++){ 
      for(ll y = 0; y <= 1000; y++){
        if(min(x, y) > a[i]) res += ((dp[l][x][0] * dp[r][y][1]) % mod * (min(x, y) - a[i])) % mod, res %= mod;
        if(min(x, y) > b[i]) res += ((dp[l][x][0] * dp[r][y][1]) % mod * (min(x, y) - b[i])) % mod, res %= mod;
      }
    }
  }
  cout << res;
}

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