Submission #1219456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219456		omsincoconut	Flooding Wall (BOI24_wall)	C++17	36 / 100	303 ms	157880 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 1e4+5, MAXA = 1e3+5;
const ll MOD = 1e9+7;

ll pf[MAXN][MAXA], sf[MAXN][MAXA];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    int a[N+2], b[N+2];
    for (int i = 1; i <= N; i++) cin >> a[i];
    for (int i = 1; i <= N; i++) cin >> b[i];

    pf[0][0] = sf[N+1][1] = 1;
    
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < MAXA; j++) {
            pf[i][max(j, a[i])] += pf[i-1][j];
            pf[i][max(j, a[i])] %= MOD;
            pf[i][max(j, b[i])] += pf[i-1][j];
            pf[i][max(j, b[i])] %= MOD;
        }
    }

    for (int i = N; i >= 1; i--) {
        for (int j = 0; j < MAXA; j++) {
            sf[i][max(j, a[i])] += sf[i+1][j];
            sf[i][max(j, a[i])] %= MOD;
            sf[i][max(j, b[i])] += sf[i+1][j];
            sf[i][max(j, b[i])] %= MOD;
        }
    }

    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        ll pq[MAXA], sq[MAXA];
        pq[MAXA-1] = pf[i-1][MAXA-1];
        sq[MAXA-1] = sf[i+1][MAXA-1];
        for (int j = MAXA-2; j > a[i]; j--) {
            pq[j] = (pq[j+1] + pf[i-1][j])%MOD;
            sq[j] = (sq[j+1] + sf[i+1][j])%MOD;

            ll val = j-a[i];
            ans += pf[i-1][j]*sq[j+1]%MOD*val;
            ans += pq[j+1]*sf[i+1][j]%MOD*val;
            ans += pf[i-1][j]*sf[i+1][j]%MOD*val;
            ans %= MOD;
        }

        for (int j = MAXA-2; j > b[i]; j--) {
            pq[j] = (pq[j+1] + pf[i-1][j])%MOD;
            sq[j] = (sq[j+1] + sf[i+1][j])%MOD;

            ll val = j-b[i];
            ans += pf[i-1][j]*sq[j+1]%MOD*val;
            ans += pq[j+1]*sf[i+1][j]%MOD*val;
            ans += pf[i-1][j]*sf[i+1][j]%MOD*val;
            ans %= MOD;
        }
    }

    cout << ans;

    return 0;
}

/*
4
1 1 1 1
2 2 2 2

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
*/

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