Submission #1141835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141835		Rafiullah	Flooding Wall (BOI24_wall)	C++20	0 / 100	3 ms	3656 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]);
    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));
    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;
    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 = 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], es[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-1]))%mod) * max(0ll,t - a[i]) ;left%=mod;
            int right=((f[i-1][t]*(es[i+1][m]-es[i+1][t-1]))%mod)*max(0ll,t-b[i]);right %=mod;
            ans += left + right, ans %= mod;
            left = (((s[i-1][m]-s[i-1][t])*e[i+1][t])%mod) * max(0ll,t-a[i]) , left %= mod;
            right = (((s[i-1][m]-s[i-1][t])*e[i+1][t])%mod) * max(0ll, t-b[i]),right%= mod;
            ans += left + right, 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: 0 / 17
• Subtask 3: 0 / 19
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30