Submission #1038119

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

Main

#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[10002][20002];
int dpr[10002][20002];
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];
    vector<int>hi;
    hi.push_back(0);
    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();
    long long 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--)
        {
            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++)
        {
            dpl[i][j]+=dpl[i-1][j];
            if(dpl[i][j]>=mod)
            dpl[i][j]-=mod;
        }
        for(int j=brr[i];j>=0;j--)
        {
            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++)
        {
            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--)
        {
            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++)
        {
            dpr[i][j]+=dpr[i+1][j];
            if(dpr[i][j]>=mod)
            dpr[i][j]-=mod;
        }
        for(int j=brr[i];j>=0;j--)
        {
            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++)
        {
            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;
            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 x=getsuml(i-1,j,j);
                x*=getsumr(i+1,j,a7a);
                x%=mod;
                ans+=((hi[j]-hi[brr[i]])*x)%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