제출 #1141682

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

Main

#include <bits/stdc++.h>
#define endl '\n'
#define ld long double
#define pb push_back
#define pf push_front
#define mod 1000000007
#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][10],suf[N][10],presum[N][10],sufsum[N][10];
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];
    pre[0][0]=1;
    suf[n+1][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=a[i]+1;j<=9;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<=9;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=9;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<=9;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<=9;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=9;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<=9;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<=9;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