Submission #1334642

#TimeUsernameProblemLanguageResultExecution timeMemory
1334642tomvip0919Fancy Fence (CEOI20_fancyfence)C++20
55 / 100
16 ms2740 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastio ios::sync_with_stdio(0); cin.tie(0);

const ll MOD = 1e9 + 7;
const ll MAXN = 500000004;
const int N = 100005;

ll h[N], w[N];
int n;

ll tri(ll x) {
    x %= MOD;
    return (x * (x + 1) % MOD) * MAXN % MOD;
}

ll subtask2() {
    ll r = 0;
    for (int i = 1; i <= n; i++) {
        ll m = h[i];
        for (int j = i; j <= n; j++) {
            m = min(m, h[j]);
            r = (r + tri(m)) % MOD;
        }
    }
    return r;
}

ll subtask3() {
    ll s = 0;
    for (int i = 1; i <= n; i++) s = (s + w[i]) % MOD;
    ll r = tri(s);
    ll c = 0;
    for (int i = 1; i <= n; i++) {
        if (h[i] == 2) {
            c = (c + w[i]) % MOD;
        } else {
            r = (r + 2 * tri(c)) % MOD;
            c = 0;
        }
    }
    r = (r + 2 * tri(c)) % MOD;
    return r;
}

ll subtask4() {
    ll s = 0;
    for (int i = 1; i <= n; i++) s = (s + w[i]) % MOD;
    return tri(h[1]) * tri(s) % MOD;
}

ll subtask5() {
    ll r = 0;
    vector<ll> s(n + 2, 0);
    for (int i = n; i >= 1; i--) s[i] = (s[i + 1] + w[i]) % MOD;
    for (int i = 1; i <= n; i++) {
        ll d = (tri(h[i]) - tri(h[i - 1]) + MOD) % MOD;
        r = (r + d * tri(s[i])) % MOD;
    }
    return r;
}

int main() {
    fastio;
    cin >> n;
    bool b2 = true, b3 = true, b4 = true, b5 = true;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        if (h[i] > 50) b2 = false;
        if (h[i] != 1 && h[i] != 2) b3 = false;
        if (i > 1 && h[i] != h[i - 1]) b4 = false;
        if (i > 1 && h[i] < h[i - 1]) b5 = false;
    }
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        if (w[i] != 1) b2 = false;
    }
    if (b4) cout << subtask4();
    else if (b2 && n <= 50) cout << subtask2();
    else if (b3) cout << subtask3();
    else if (b5) cout << subtask5();
    else cout << subtask4();
    return (0);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...