Submission #968199

#	Time	Username	Problem	Language	Result	Execution time	Memory
968199		weakweakweak	Real Mountains (CCO23_day1problem2)	C++17	0 / 25	0 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;


#define fs first
#define sc second

int n, a[20100], o[5100];


int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    set<pii>st;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> o[i];
        st.insert({o[i], i});
    }

    long long ans = 0;
    int target = min(o[1], o[n]);
    for (int h = 1; h <= 100; h++) {
        if (h > target) break;
        int ll[5010], rr[5010];
        ll[0] = rr[n + 1] = INT_MAX;
        for (int i = 1; i <= n; i++) {
            ll[i] = ll[i - 1];
            if (o[i] == h - 1) continue;
            ll[i] = min(ll[i - 1], o[i]);
        }
        for (int i = n; i >= 1; i--) {
            rr[i] = rr[i + 1];
            if (o[i] == h - 1) continue;
            rr[i] = min(rr[i + 1], o[i]);
        }
        vector <int> v;
        for (int i = 1; i <= n; i++) if (o[i] == h - 1) v.push_back(i);
        if (v.size() == 0) continue;
        if (v.size() == 1) {
            int i = v[0];
            ans += ll[i - 1] * (h - 1) * rr[i + 1];
            o[i] = h;
            continue;}
        int z = min(ll[v[0] - 1] * (h - 1) * rr[v[0] + 1] + h * (h - 1) * rr[v.back() + 1],
                    ll[v.back() - 1] * (h - 1) * rr[v.back() + 1] + ll[v[0] - 1] * (h - 1) * h);
        z += (v.size() - 2) * (h - 1) * 1LL * h * h;
        ans += z;
        // cout << ll[v[0] - 1] * (h - 1) * rr[v[0] + 1] + h * (h - 1) * rr[v.back() + 1] << ' ' << 
        //             ll[v.back() - 1] * (h - 1) * rr[v.back() + 1] + ll[v[0] - 1] * (h - 1) * h << "   ";
        // cout << h << ' ' << z << '\n';
        for (int x : v) o[x] = h;
    }

    cout << ans % (1000000 + 3) << '\n';
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 3
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 4