Submission #1096092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096092		epicci23	Flooding Wall (BOI24_wall)	C++17	56 / 100	5053 ms	41668 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int MOD = 1000000007;

void _(){
  int n;cin >> n;
  int ar[n+5][2];
  for(int i=1;i<=n;i++) cin >> ar[i][0];
  for(int i=1;i<=n;i++) cin >> ar[i][1];
  
  vector<int> zip;
  for(int i=1;i<=n;i++){
   for(int j=0;j<2;j++)
  	zip.push_back(ar[i][j]);
  }

  sort(all(zip));
  zip.erase(unique(all(zip)),zip.end());
  int ans=0;
 
  int pre_dp[n+5][3],suf_dp[n+5][3];

  for(int x:zip){
  for(int j=0;j<3;j++) pre_dp[0][j]=suf_dp[n+1][j]=0;
  suf_dp[n+1][0]=pre_dp[0][0]=1;
   for(int i=1;i<=n;i++){
   	for(int j=0;j<3;j++) pre_dp[i][j]=0;
   	for(int j=0;j<2;j++){
   	  int u=ar[i][j];
   	  if(u>x)
   	  	pre_dp[i][2]+=pre_dp[i-1][0]+pre_dp[i-1][1]+pre_dp[i-1][2];
   	  else if(u==x){
   	  	pre_dp[i][1]+=pre_dp[i-1][0]+pre_dp[i-1][1];
   	  	pre_dp[i][2]+=pre_dp[i-1][2];
   	  }
   	  else{
   	  	pre_dp[i][2]+=pre_dp[i-1][2];
   	  	pre_dp[i][1]+=pre_dp[i-1][1];
   	  	pre_dp[i][0]+=pre_dp[i-1][0];
   	  }
   	}
   	for(int j=0;j<3;j++) pre_dp[i][j]%=MOD;
   }
   
   for(int i=n;i>=1;i--){
   	for(int j=0;j<3;j++) suf_dp[i][j]=0;
   	for(int j=0;j<2;j++){
   	  int u=ar[i][j];
   	  if(u>x)
   	  	suf_dp[i][2]+=suf_dp[i+1][0]+suf_dp[i+1][1]+suf_dp[i+1][2];
   	  else if(u==x){
   	  	suf_dp[i][1]+=suf_dp[i+1][0]+suf_dp[i+1][1];
   	  	suf_dp[i][2]+=suf_dp[i+1][2];
   	  }
   	  else{
   	  	suf_dp[i][2]+=suf_dp[i+1][2];
   	  	suf_dp[i][1]+=suf_dp[i+1][1];
   	  	suf_dp[i][0]+=suf_dp[i+1][0];
   	  }
   	}
   	for(int j=0;j<3;j++) suf_dp[i][j]%=MOD;
   }

   for(int i=2;i<n;i++){
    for(int j=0;j<2;j++){
      int u=ar[i][j];
      if(u>=x) continue;
      ans+=(((x-u)*suf_dp[i+1][1])%MOD*pre_dp[i-1][1])%MOD;
      ans+=(((x-u)*suf_dp[i+1][2])%MOD*pre_dp[i-1][1])%MOD;
      ans+=(((x-u)*suf_dp[i+1][1])%MOD*pre_dp[i-1][2])%MOD;
      ans%=MOD;
    }
   }
  }

  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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