oj.uz

Submission #968199

# Submission time Handle Problem Language Result Execution time Memory
968199 2024-04-23T08:27:15 Z weakweakweak Real Mountains (CCO23_day1problem2) C++17
0 / 25
 0 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -