Submission #1155866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155866		adiyer	Flooding Wall (BOI24_wall)	C++20	44 / 100	5053 ms	784876 KiB

Main

#pragma optimize ("g",on)
#pragma GCC optimize("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")

#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 = 2e4 + 11;
const int P = 31;
const int mod = 1e9 + 7;
const ll inf = 1e18;

int n, sz, res, x, i, j, l, r, cur1, cur2;
int a[N], b[N], ia[N], ib[N], p[MAX], s[MAX], val[MAX]; 

int dp[N][MAX];

vector < int > c;

map < int, int > mp;

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  for(i = 1; i <= n; i++) cin >> a[i], c.pb(a[i]);
  for(i = 1; i <= n; i++) cin >> b[i], c.pb(b[i]);
  sort(all(c));
  for(int vl : c)
    if(!mp[vl])
      mp[vl] = ++sz, val[sz] = vl;
  for(i = 1; i <= n; i++) ia[i] = a[i], a[i] = mp[a[i]], ib[i] = b[i], b[i] = mp[b[i]];
  dp[0][0] = 1;
  for(x = 0; x <= sz; x++) p[x] = 1;
  for(i = 1; i <= n; i++){
    for(x = sz; x >= 0; x--){
      int &y = dp[i][x];
      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];
      }
      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];
        else y = dp[i - 1][x] * 2;
      }
      y %= mod;
    }
    for(x = 0; x <= sz; x++){
      if(x) p[x] = (p[x - 1] + dp[i][x]) % mod;
      else p[x] = dp[i][x];
    }
  }
  dp[n + 1][0] = 1;
  for(x = 0; x <= sz; x++) p[x] = 1;
  for(i = n; i >= 1; i--){
    for(x = sz; x >= 0; x--){
      int &y = dp[i][x];
      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];
      }
      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];
        else y = dp[i + 1][x] * 2;
      }
      y %= mod;
    }
    for(x = 0; x <= sz; x++){
      if(x) p[x] = (p[x - 1] + dp[i][x]) % mod;
      else p[x] = dp[i][x];
    }
    if(1 < i && i < n){
      l = i - 1, r = i + 1, cur1 = 0, cur2 = 0;
      for(x = sz; x >= 0; x--){
        s[x] = (s[x + 1] + dp[r][x]) % mod;
      }
      for(x = 0; x <= sz; x++){ 
        res += (dp[l][x] * 1ll * cur1) % mod, res %= mod;
        res += (dp[l][x] * 1ll * cur2) % mod, res %= mod;
        if(x > a[i]) 
          res += ((dp[l][x] * 1ll * s[x]) % mod * 1ll * (val[x] - ia[i])) % mod, res %= mod, 
          cur1 += (dp[r][x] * 1ll * (val[x] - ia[i])) % mod, cur1 %= mod;
        if(x > b[i]) 
          res += ((dp[l][x] * 1ll * s[x]) % mod * 1ll * (val[x] - ib[i])) % mod, res %= mod,
          cur2 += (dp[r][x] * 1ll * (val[x] - ib[i])) % mod, cur2 %= mod;
      }
    }
  }
  cout << res;
}

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