제출 #1096090

#제출 시각아이디문제언어결과실행 시간메모리
1096090epicci23Flooding Wall (BOI24_wall)C++17
56 / 100
5041 ms41668 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){ 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]+=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<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; }
#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...