제출 #1141704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141704		hashimali	Flooding Wall (BOI24_wall)	C++20	0 / 100	159 ms	436 KiB

Main

#include <bits/stdc++.h>
#define endl '\n'
#define ld long double
#define pb push_back
#define pf push_front
#define mod 50000007
#define se second
#define fi first
#define all(ls) (ls).begin(),(ls).end()
#define int long long
using namespace std;
void solve(){
    int n;
    cin>>n;
    int maxi=0;
    int a[n+10],b[n+10];
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxi=max(maxi,a[i]);
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        maxi=max(maxi,b[i]);
    }
    maxi+=2;
    if(n<=20){
        int ways=0;
        int p[n+10],s[n+10],cur[n+10];
        for(int mask=0;mask<(1<<n);mask++){
            for(int i=0;i<n;i++)
                if(mask&(1<<i))
                    cur[i+1]=a[i+1];
                else
                    cur[i+1]=b[i+1];
            p[0]=0;s[n+1]=0;
            for(int i=1;i<=n;i++)
                p[i]=max(p[i-1],cur[i]);
            for(int i=n;i>=1;i--){
                s[i]=max(s[i+1],cur[i]);
                ways=(ways+(min(p[i],s[i])-cur[i]))%mod;
            }
        }
        cout<<ways<<endl;
        return;
    }
    vector<vector<int>>pre(vector<vector<int>>(n+10,vector<int>(maxi+9)));
    vector<vector<int>>suf(vector<vector<int>>(n+10,vector<int>(maxi+9)));
    vector<vector<int>>presum(vector<vector<int>>(n+10,vector<int>(maxi+9)));
    vector<vector<int>>sufsum(vector<vector<int>>(n+10,vector<int>(maxi+9)));
    pre[0][0]=1;
    suf[n+1][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=a[i]+1;j<=maxi;j++)
            pre[i][j]=(pre[i][j]+pre[i-1][j])%mod;
        for(int j=0;j<=a[i];j++)
            pre[i][a[i]]=(pre[i][a[i]]+pre[i-1][j])%mod;
        for(int j=b[i]+1;j<=maxi;j++)
            pre[i][j]=(pre[i][j]+pre[i-1][j])%mod;
        for(int j=0;j<=b[i];j++)
            pre[i][b[i]]=(pre[i][b[i]]+pre[i-1][j])%mod;
        for(int j=maxi;j>=0;j--)
            presum[i][j]=(presum[i][j+1]+pre[i][j])%mod;
    }
    for(int i=n;i>=1;i--){
        for(int j=a[i]+1;j<=maxi;j++)
            suf[i][j]=(suf[i][j]+suf[i+1][j])%mod;
        for(int j=0;j<=a[i];j++)
            suf[i][a[i]]=(suf[i][a[i]]+suf[i+1][j])%mod;
        for(int j=b[i]+1;j<=maxi;j++)
            suf[i][j]=(suf[i][j]+suf[i+1][j])%mod;
        for(int j=0;j<=b[i];j++)
            suf[i][b[i]]=(suf[i][b[i]]+suf[i+1][j])%mod;
        for(int j=maxi;j>=0;j--)
            sufsum[i][j]=(sufsum[i][j+1]+suf[i][j])%mod;
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=0;j<10;j++)
    //         cout<<pre[i][j]<<" ";
    //     cout<<endl;
    // }
    // cout<<endl;
    // for(int i=1;i<=n;i++){
    //     for(int j=0;j<10;j++)
    //         cout<<suf[i][j]<<" ";
    //     cout<<endl;
    // }
    // cout<<endl;
    // for(int i=1;i<=n;i++){
    //     for(int j=0;j<10;j++)
    //         cout<<presum[i][j]<<" ";
    //     cout<<endl;
    // }
    // cout<<endl;
    // for(int i=1;i<=n;i++){
    //     for(int j=0;j<10;j++)
    //         cout<<sufsum[i][j]<<" ";
    //     cout<<endl;
    // }
    // cout<<endl;
    int ways=0;
    for(int i=1;i<=n;i++){
        for(int j=a[i]+1;j<=maxi;j++){
            ways=(ways+(((pre[i-1][j]*sufsum[i+1][j+1])%mod)*(j-a[i]))%mod)%mod;
            ways=(ways+(((suf[i+1][j]*presum[i-1][j+1])%mod)*(j-a[i]))%mod)%mod;
            ways=(ways+(((pre[i-1][j]*suf[i+1][j])%mod)*(j-a[i]))%mod)%mod;
        }
        for(int j=b[i]+1;j<=maxi;j++){
            ways=(ways+(((pre[i-1][j]*sufsum[i+1][j+1])%mod)*(j-b[i]))%mod)%mod;
            ways=(ways+(((suf[i+1][j]*presum[i-1][j+1])%mod)*(j-b[i]))%mod)%mod;
            ways=(ways+(((pre[i-1][j]*suf[i+1][j])%mod)*(j-b[i]))%mod)%mod;
        }
    }
    cout<<ways<<endl;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    for(int i=1;i<=t;i++){
        // cout<<"Scenario #"<<i<<":"<<" ";
        solve();
    }
}

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