제출 #1141692

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141692		hashimali	Flooding Wall (BOI24_wall)	C++20	0 / 100	0 ms	580 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;
const int N=6e5+10;
int a[N],b[N];
int pre[N][100],suf[N][100],presum[N][100],sufsum[N][100];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>b[i];
    // 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;
    // }
    pre[0][0]=1;
    suf[n+1][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=a[i]+1;j<=50;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<=50;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=50;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<=50;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<=50;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=50;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<=50;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<=50;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