제출 #1096086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1096086		epicci23	Flooding Wall (BOI24_wall)	C++17	56 / 100	5056 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;

int add(int a,int b){
 if(a+b>=MOD) return a+b-MOD;
 return a+b;
}

int mult(int a,int b){
  if(a*b>=MOD) return a*b%MOD;
  return a*b;
}

int fast(int a,int b){
 if(b==0) return 1;
 int res=fast(a,b/2);
 res=mult(res,res);
 if(b&1) res=mult(res,a);
 return res;
}

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;
 
  for(int x:zip){
   int pre_dp[n+5][3],suf_dp[n+5][3];
   memset(pre_dp,0,sizeof(pre_dp));
   memset(suf_dp,0,sizeof(suf_dp));
   suf_dp[n+1][0]=pre_dp[0][0]=1;
   for(int i=1;i<=n;i++){
   	for(int j=0;j<2;j++){
   	  int u=ar[i][j];
   	  if(u>x)
   	  	pre_dp[i][2]=add(pre_dp[i][2],add(pre_dp[i-1][0],add(pre_dp[i-1][1],pre_dp[i-1][2])));
   	  else if(u==x){
   	  	pre_dp[i][1]=add(pre_dp[i][1],add(pre_dp[i-1][0],pre_dp[i-1][1]));
   	  	pre_dp[i][2]=add(pre_dp[i][2],pre_dp[i-1][2]);
   	  }
   	  else{
   	  	pre_dp[i][2]=add(pre_dp[i][2],pre_dp[i-1][2]);
   	  	pre_dp[i][1]=add(pre_dp[i][1],pre_dp[i-1][1]);
   	  	pre_dp[i][0]=add(pre_dp[i][0],pre_dp[i-1][0]);
   	  }
   	}
   }
   
   for(int i=n;i>=1;i--){
   	for(int j=0;j<2;j++){
   	  int u=ar[i][j];
   	  if(u>x)
   	  	suf_dp[i][2]=add(suf_dp[i][2],add(suf_dp[i+1][0],add(suf_dp[i+1][1],suf_dp[i+1][2])));
   	  else if(u==x){
   	  	suf_dp[i][1]=add(suf_dp[i][1],add(suf_dp[i+1][0],suf_dp[i+1][1]));
   	  	suf_dp[i][2]=add(suf_dp[i][2],suf_dp[i+1][2]);
   	  }
   	  else{
   	  	suf_dp[i][2]=add(suf_dp[i][2],suf_dp[i+1][2]);
   	  	suf_dp[i][1]=add(suf_dp[i][1],suf_dp[i+1][1]);
   	  	suf_dp[i][0]=add(suf_dp[i][0],suf_dp[i+1][0]);
   	  }
   	}
   }


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

  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