Submission #1038171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038171		Mr_Ph	Flooding Wall (BOI24_wall)	C++17	25 / 100	1614 ms	1048576 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int mod=(int)1e9+7;
vector<vector<int>>dpl;
vector<vector<int>>dpr;
int getsuml(int i,int l,int r)
{
    if((dpl[i][r]-dpl[i][l-1]+mod)>=mod)return(dpl[i][r]-dpl[i][l-1]);
    else return (dpl[i][r]-dpl[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;
    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];
    vector<int>hi;
    for(auto i:arr)hi.push_back(i);
    for(auto i:brr)hi.push_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();
    dpl.resize(n+2);
    dpr.resize(n+2);
    for(int i=0;i<=n+1;i++)
    {
        dpl[i].resize(a7a+2);
        dpr[i].resize(a7a+2);
    }
    int ans=0;
    // cout<<dpl.size();
    // return 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];
            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];
            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];
            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];
            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];
            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;
        }
    }
    // 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=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;
        }
        for(int j=brr[i];j<=a7a;j++)
        {
            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;
}

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