제출 #1038237

#제출 시각아이디문제언어결과실행 시간메모리
1038237Mr_PhFlooding Wall (BOI24_wall)C++17
0 / 100
11 ms2396 KiB
#include<bits/stdc++.h> using namespace std; const int mod=(int)1e9+7; int dpl[2][20003]; int pref[2][20003]; int dpr[10003][20003]; vector<int>hi; int arr[10000+1]; int brr[10000+1]; int getsuml(int i,int l,int r) { i%=2; if((pref[i][r]-pref[i][l-1]+mod)>=mod)return(pref[i][r]-pref[i][l-1]); else return (pref[i][r]-pref[i][l-1]+mod); } int getsumr(int i,int l,int r) { if((dpr[i][r]-dpr[i][l-1]+mod)>=mod)return (dpr[i][r]-dpr[i][l-1]); else return (dpr[i][r]-dpr[i][l-1]+mod); } signed main() { int n; cin>>n; for(int i=1;i<=n;i++)cin>>arr[i]; for(int i=1;i<=n;i++){ cin>>brr[i]; if(arr[i]>brr[i])swap(arr[i],brr[i]); } for(int i=1;i<=n;i++)hi.push_back(arr[i]); for(int i=1;i<=n;i++)hi.push_back(brr[i]); hi.push_back(0); sort(hi.begin(),hi.end()); hi.erase(unique(hi.begin(),hi.end())); int a7a=*max_element(arr,arr+n+1); a7a=max(a7a,*max_element(brr,brr+n+1)); a7a=lower_bound(hi.begin(),hi.end(),a7a)-hi.begin(); int ans=0; // cout<<dpl.size(); // return 0; dpr[n+1][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=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]; 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]; 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]; 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]; dpr[i][j]%=mod; } } dpl[0][0]=1; pref[0][0]=1; for(int i=0;i<=n+1;i++) for(int j=1;j<=a7a;j++){ pref[0][j]=dpl[0][j]+pref[0][j-1]; if(pref[0][j]>=mod) pref[0][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=0;j<=a7a;j++)dpl[i%2][j]=0,pref[i%2][j]=0; for(int j=arr[i];j>=0;j--) { if(dpl[(i%2)^1][j]==0)continue; dpl[i%2][arr[i]]+=dpl[(i%2)^1][j]; dpl[i%2][arr[i]]%=mod; } for(int j=arr[i]+1;j<=a7a;j++) { if(dpl[(i%2)^1][j]==0)continue; dpl[i%2][j]+=dpl[(i%2)^1][j]; dpl[i%2][j]%=mod; } for(int j=brr[i];j>=0;j--) { if(dpl[(i%2)^1][j]==0)continue; dpl[i%2][brr[i]]+=dpl[(i%2)^1][j]; dpl[i%2][brr[i]]%=mod; } for(int j=brr[i]+1;j<=a7a;j++) { if(dpl[(i%2)^1][j]==0)continue; dpl[i%2][j]+=dpl[(i%2)^1][j]; dpl[i%2][j]%=mod; } pref[i%2][0]=dpl[i%2][0]; for(int j=1;j<=a7a;j++){ pref[i%2][j]=dpl[i%2][j]+pref[i%2][j-1]; if(pref[i%2][j]>=mod) pref[i%2][j]-=mod; } for(int j=arr[i];j<=a7a;j++) { 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]) { 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...