Submission #1038237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038237		Mr_Ph	Flooding Wall (BOI24_wall)	C++17	0 / 100	11 ms	2396 KiB

Main

#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;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 19
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30