제출 #1096096

#제출 시각아이디문제언어결과실행 시간메모리
1096096epicci23Flooding Wall (BOI24_wall)C++17
70 / 100
5028 ms49340 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...