제출 #1141871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141871		Rafiullah	Flooding Wall (BOI24_wall)	C++20	36 / 100	415 ms	316040 KiB

Main

#include<bits/stdc++.h>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
#define int long long
const int N = 10005;
const int mod = 1e9 + 7;
const int mod1 = 998244353;
const int LG = 20;
// #define s(i) (*s.find_by_order(i)) // Warning : Read this line.
set<pair<int,int>> S;
int power(int b,int e){
    if(e<=0)return 1;
    int o = power(b,e>>1);
    o *= o, o %= mod1;
    if(e % 2)o *= b, o %= mod1;
    return o;
}
int a[N], b[N];
void solve(){
    int n;cin >> n ;int m = 0;
    for(int i = 1 ; i <= n ; i ++)
        cin >> a[i], m = max(m,a[i]);
    for(int i = 1 ; i <= n ; i ++)
        cin >> b[i], m = max(m,b[i]);
    for(int i = 1 ; i <= n ;i  ++)
        if(a[i] > b[i])swap(a[i],b[i]);
    if(n <= 20){int ans = 0;
        for(int i = 0 ; i < (1LL << n) ; i ++){
            vector<int> t(n + 2);
            for(int j = 0 ; j < n ; j ++)
                if(i & (1LL << j))t[j + 1] = b[j+1];
                else t[j + 1] = a[j+1];
            vector<int> suf(n + 2);
            suf[n]=t[n];
            for(int j = n - 1 ; j >= 1;  j--)
                suf[j]=max(suf[j+1],t[j]);
            int p = t[1];int o = 0;
            for(int j = 2 ; j < n ; j ++){
                o += max(0ll,min(p,suf[j+1]) - t[j]) ,o%=mod;
                p=max(p,t[j]);
            }
            ans += o;
        }
        cout << ans << '\n';return;
    }
    vector<vector<int>> f(n + 2,vector<int>(m + 2));
    vector<vector<int>> s(n + 2,vector<int>(m + 2));
    vector<vector<int>> e(n + 2,vector<int>(m + 2));    
    vector<vector<int>> es(n + 2,vector<int>(m + 2));
    // vector<vector<int>> suf(n + 2, vector<int>(m + 2));
    f[1][a[1]] = 1;
    f[1][b[1]] = 1;
    s[1][a[1]] = 1;
    s[1][b[1]] = 1;
    for(int i = 1 ; i <= m ; i ++)s[1][i] += s[1][i-1];
    for(int i = 2 ; i <= n ; i ++){
        for(int j = 1 ; j <= m ; j ++){
            if(a[i] < j)
                f[i][j] += f[i - 1][j];
            else if(a[i] == j)
                f[i][j] += s[i - 1][j];
            f[i][j] %= mod;
            if(b[i] < j)
                f[i][j] += f[i - 1][j];
            else if(b[i] == j)
                f[i][j] += s[i - 1][j];
            f[i][j] %= mod;
            s[i][j] += s[i][j-1] + f[i][j], s[i][j] %= mod;
        }
    }
    e[n][a[n]] = 1;
    e[n][b[n]] = 1;
    // suf[n][a[n]] = suf[n][b[n]] = 1;
    es[n][a[n]] = es[n][b[n]] = 1;
    for(int i = 1 ; i <= m ; i ++)
        es[n][i] += es[n][i - 1];
    // for(int i = m ; i >= 1 ; i --)
    //     suf[n][i] += suf[n][i+1];
    for(int i = n - 1 ; i >= 1 ; i --){
        for(int j = 1 ; j <= m ; j ++){
            if(a[i] < j)
                e[i][j] += e[i + 1][j];
            else if(a[i] == j)
                e[i][j] += es[i + 1][j];
            e[i][j] %= mod;
            if(b[i] < j)
                e[i][j] += e[i + 1][j];
            else if(b[i] == j)
                e[i][j] += es[i + 1][j];
            e[i][j] %= mod;
            es[i][j] += (es[i][j - 1] + e[i][j])%mod, es[i][j] %= mod;
        }
        // for(int j = m ; j >= 1 ; j --)
        //     suf[i][j] += suf[i][j+1] + e[i][j],suf[i][j] %= mod; 
    }
    int ans = 0;
    for(int i = 2 ; i < n ; i ++){
        for(int t = 1 ; t <= m ; t ++){
            int ho = m - t + 1;
            int left = ((f[i-1][t]*(es[i+1][m]-es[i+1][t]))%mod) * max(0ll,t - a[i]) %mod;left%=mod;
            int right=((f[i-1][t]*(es[i+1][m]-es[i+1][t]))%mod)*max(0ll,t-b[i])%mod;right %=mod;
            ans += (left + right)%mod, ans %= mod;
        }
        for(int t = 1 ; t <= m ; t ++){
            int left = (((s[i-1][m]-s[i-1][t-1])*e[i+1][t])%mod) * max(0ll,t-a[i]) ; left %= mod;
            int right = (((s[i-1][m]-s[i-1][t-1])*e[i+1][t])%mod) * max(0ll, t-b[i]);right%= mod;
            ans += (left + right)%mod, ans %= mod;
        }
    }
    cout << ans << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t --){
        solve();
    }
}

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