Submission #1155845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155845		adiyer	Flooding Wall (BOI24_wall)	C++20	44 / 100	485 ms	1114112 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;

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

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]];
  int dp[N][sz + 5][2] = {};
  for(int 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(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][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(x = 0; x <= sz; 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(i = 2; i < n; i++){
    l = i - 1, r = n - i, cur1 = 0, cur2 = 0;
    for(x = sz; x >= 0; x--){
      s[x] = (s[x + 1] + dp[r][x][1]) % mod;
    }
    for(x = 0; x <= sz; x++){ 
      res += (dp[l][x][0] * 1ll * cur1) % mod, res %= mod;
      res += (dp[l][x][0] * 1ll * cur2) % mod, res %= mod;
      if(x > a[i]) 
        res += ((dp[l][x][0] * 1ll * s[x]) % mod * 1ll * (val[x] - ia[i])) % mod, res %= mod, 
        cur1 += (dp[r][x][1] * 1ll * (val[x] - ia[i])) % mod, cur1 %= mod;
      if(x > b[i]) 
        res += ((dp[l][x][0] * 1ll * s[x]) % mod * 1ll * (val[x] - ib[i])) % mod, res %= mod,
        cur2 += (dp[r][x][1] * 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