Submission #1096096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096096		epicci23	Flooding Wall (BOI24_wall)	C++17	70 / 100	5028 ms	49340 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;
   	  if(ar[i][0]>x)
   	  	pre_dp[i][2]+=pre_dp[i-1][0]+pre_dp[i-1][1]+pre_dp[i-1][2];
   	  else if(ar[i][0]==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];
   	  }

   	  if(ar[i][1]>x)
   	  	pre_dp[i][2]+=pre_dp[i-1][0]+pre_dp[i-1][1]+pre_dp[i-1][2];
   	  else if(ar[i][1]==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;

   	  if(ar[i][0]>x)
   	  	suf_dp[i][2]+=suf_dp[i+1][0]+suf_dp[i+1][1]+suf_dp[i+1][2];
   	  else if(ar[i][0]==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];
   	  }
      
   	  if(ar[i][1]>x)
   	  	suf_dp[i][2]+=suf_dp[i+1][0]+suf_dp[i+1][1]+suf_dp[i+1][2];
   	  else if(ar[i][1]==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++){
      int lmao = max(0LL,x-ar[i][0]) + max(0LL,x-ar[i][1]);
      int xd = 0;
      xd+=suf_dp[i+1][1]*pre_dp[i-1][1];
      xd+=suf_dp[i+1][2]*pre_dp[i-1][1];
      xd+=suf_dp[i+1][1]*pre_dp[i-1][2];
      xd%=MOD;
      ans+=xd*lmao;
      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: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 30