제출 #1038160

#제출 시각아이디문제언어결과실행 시간메모리
1038160Mr_PhFlooding Wall (BOI24_wall)C++17
25 / 100
5064 ms1048576 KiB
#include<bits/stdc++.h> // #define int long long #pragma GCC optimize("Ofast") #define endl '\n' using namespace std; const int mod=(int)1e9+7; int dpl[10003][20001]; int dpr[10003][20001]; vector<int>hi; int getsuml(int i,int l,int r) { return (dpl[i][r]-dpl[i][l-1]+mod)%mod; } int getsumr(int i,int l,int r) { return (dpr[i][r]-dpr[i][l-1]+mod)%mod; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin>>n; vector<int>arr(n+1); vector<int>brr(n+1); for(int i=1;i<=n;i++)cin>>arr[i]; for(int i=1;i<=n;i++)cin>>brr[i]; hi.push_back(0); for(auto i:arr)hi.emplace_back(i); for(auto i:brr)hi.emplace_back(i); sort(hi.begin(),hi.end()); hi.erase(unique(hi.begin(),hi.end())); int a7a=*max_element(arr.begin(),arr.end()); a7a=max(a7a,*max_element(brr.begin(),brr.end())); a7a=lower_bound(hi.begin(),hi.end(),a7a)-hi.begin(); int ans=0; dpl[0][0]=1; for(int i=1;i<=n;i++)arr[i]=lower_bound(hi.begin(),hi.end(),arr[i])-hi.begin(),brr[i]=lower_bound(hi.begin(),hi.end(),brr[i])-hi.begin(); for(int i=1;i<=n;i++) { for(int j=arr[i];j>=0;j--) { if(dpl[i-1][j]==0)continue; dpl[i][arr[i]]+=dpl[i-1][j]; if(dpl[i][arr[i]]>=mod) dpl[i][arr[i]]-=mod; } for(int j=arr[i]+1;j<=a7a;j++) { if(dpl[i-1][j]==0)continue; dpl[i][j]+=dpl[i-1][j]; if(dpl[i][j]>=mod) dpl[i][j]-=mod; } for(int j=brr[i];j>=0;j--) { if(dpl[i-1][j]==0)continue; dpl[i][brr[i]]+=dpl[i-1][j]; if(dpl[i][brr[i]]>=mod) dpl[i][brr[i]]-=mod; } for(int j=brr[i]+1;j<=a7a;j++) { if(dpl[i-1][j]==0)continue; dpl[i][j]+=dpl[i-1][j]; if(dpl[i][j]>=mod) dpl[i][j]-=mod; } } dpr[n+1][0]=1; for(int i=n;i>=1;i--) { for(int j=arr[i];j>=0;j--) { if(dpr[i+1][j]==0)continue; dpr[i][arr[i]]+=dpr[i+1][j]; if(dpr[i][arr[i]]>=mod) dpr[i][arr[i]]-=mod; } for(int j=arr[i]+1;j<=a7a;j++) { if(dpr[i+1][j]==0)continue; dpr[i][j]+=dpr[i+1][j]; if(dpr[i][j]>=mod) dpr[i][j]-=mod; } for(int j=brr[i];j>=0;j--) { if(dpr[i+1][j]==0)continue; dpr[i][brr[i]]+=dpr[i+1][j]; if(dpr[i][brr[i]]>=mod) dpr[i][brr[i]]-=mod; } for(int j=brr[i]+1;j<=a7a;j++) { if(dpr[i+1][j]==0)continue; dpr[i][j]+=dpr[i+1][j]; if(dpr[i][j]>=mod) dpr[i][j]-=mod; } } // cout<<ans<<endl; for(int i=0;i<=n+1;i++) for(int j=1;j<=a7a;j++){ dpl[i][j]+=dpl[i][j-1]; if(dpl[i][j]>=mod) dpl[i][j]-=mod; dpr[i][j]+=dpr[i][j-1]; if(dpr[i][j]>=mod) dpr[i][j]-=mod; } for(int i=1;i<=n;i++) { for(int j=min(arr[i],brr[i]);j<=a7a;j++) { if(j>=arr[i]){ long long x=getsuml(i-1,j,j); x*=getsumr(i+1,j,a7a); x%=mod; ans+=((hi[j]-hi[arr[i]])*x)%mod; if(ans>=mod)ans-=mod; x=getsumr(i+1,j,j); x*=getsuml(i-1,j+1,a7a); x%=mod; ans+=((hi[j]-hi[arr[i]])*x)%mod; if(ans>=mod)ans-=mod; } if(j>=brr[i]) { long long x=getsuml(i-1,j,j); x*=getsumr(i+1,j,a7a); x%=mod; ans+=((hi[j]-hi[brr[i]])*x)%mod; if(ans>=mod)ans-=mod; x=getsumr(i+1,j,j); x*=getsuml(i-1,j+1,a7a); x%=mod; ans+=((hi[j]-hi[brr[i]])*x)%mod; if(ans>=mod)ans-=mod; } } } cout<<ans<<endl; }
#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...