Submission #1095826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095826		SalihSahin	Flooding Wall (BOI24_wall)	C++14	56 / 100	5021 ms	64988 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int N = 2e5 + 5;
const int K = 20;
const int mod = 1e9 + 7;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    set<int> dfvals;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++){
        cin>>a[i];
        dfvals.insert(a[i]);
    }
    for(int i = 0; i < n; i++){
        cin>>b[i];
        dfvals.insert(b[i]);
    }
    int ans = 0;
    for(auto itr: dfvals){
        vector<vector<int> > pre(n+1, vector<int>(3)), suf(n+1, vector<int>(3)); // 0 => max < itr, 1 => max = itr, 2 => max > itr
        pre[0][0] = 1;
        for(int i = 0; i < n; i++){
            if(a[i] < itr){
                pre[i+1][0] += pre[i][0];
                pre[i+1][1] += pre[i][1];
                pre[i+1][2] += pre[i][2];
            }
            else if(a[i] == itr){
                pre[i+1][1] += pre[i][0];
                pre[i+1][1] += pre[i][1];
                pre[i+1][2] += pre[i][2];
            }
            else{
                pre[i+1][2] += (pre[i][0] + pre[i][1] + pre[i][2]);
            }
            for(int j = 0; j < 3; j++) pre[i+1][j] %= mod;

            if(b[i] < itr){
                pre[i+1][0] += pre[i][0];
                pre[i+1][1] += pre[i][1];
                pre[i+1][2] += pre[i][2];
            }
            else if(b[i] == itr){
                pre[i+1][1] += (pre[i][0] + pre[i][1]);
                pre[i+1][2] += pre[i][2];
            }
            else{
                pre[i+1][2] += (pre[i][0] + pre[i][1] + pre[i][2]);
            }
            for(int j = 0; j < 3; j++) pre[i+1][j] %= mod;
        }

        suf[n][0] = 1;
        for(int i = n-1; i >= 0; i--){
            if(a[i] < itr){
                suf[i][0] += suf[i+1][0];
                suf[i][1] += suf[i+1][1];
                suf[i][2] += suf[i+1][2];
            }
            else if(a[i] == itr){
                suf[i][1] += suf[i+1][0];
                suf[i][1] += suf[i+1][1];
                suf[i][2] += suf[i+1][2];
            }
            else{
                suf[i][2] += (suf[i+1][0] + suf[i+1][1] + suf[i+1][2]);
            }
            for(int j = 0; j < 3; j++) suf[i][j] %= mod;

            if(b[i] < itr){
                suf[i][0] += suf[i+1][0];
                suf[i][1] += suf[i+1][1];
                suf[i][2] += suf[i+1][2];
            }
            else if(b[i] == itr){
                suf[i][1] += suf[i+1][0];
                suf[i][1] += suf[i+1][1];
                suf[i][2] += suf[i+1][2];
            }
            else{
                suf[i][2] += (suf[i+1][0] + suf[i+1][1] + suf[i+1][2]);
            }
            for(int j = 0; j < 3; j++) suf[i][j] %= mod;
        }

        int add = 0;
        for(int i = 1; i < n-1; i++){
            int calc = (pre[i][1] * suf[i+1][1] + pre[i][2] * suf[i+1][1] + pre[i][1] * suf[i+1][2])%mod;
            int tot = max(0LL, itr - a[i]) + max(0LL, itr - b[i]);
            add = (add + (calc * tot)%mod)%mod;
        }
        ans = (ans + add)%mod;
    }

    cout<<ans<<endl;
    return 0;
}

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