제출 #1287629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287629		stefanneagu	Tortoise (CEOI21_tortoise)	C++20	100 / 100	104 ms	16088 KiB

tortoise

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 6e5 + 1, inf = 1e9;

int v[nmax];
int st[nmax];
int dr[nmax];
int nxt_val[nmax];

int32_t main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    int ult = 0;
    for (int i = 1; i <= n; i++) {
        if (v[i] == -1) {
            ult = i;
        }
        st[i] = ult;
    }
    ult = 0;
    int special = -1;
    int ult_bun = 0;
    for (int i = n; i >= 1; i--) {
        if (v[i] == -1) {
            ult = i;
        }
        dr[i] = ult;
        if (v[i]) {
            if (ult_bun) {
                nxt_val[i] = ult_bun;
            } else {
                special = i;
            }
            ult_bun = i;
        }
    }
    map<int, int> dists;
    int ans = 0, sum = 0;
    for (int i = 1; i <= n; i++) {
        if (v[i] <= 0) {
            continue;
        }
        ans += v[i];
        int dist = inf;
        if (st[i]) {
            dist = min(dist, (i - st[i]) * 2);
        }
        if (dr[i]) {
            dist = min(dist, (dr[i] - i) * 2);
        }
        int ult_dist = dist;
        if (dr[i] && nxt_val[i]) {
            if (nxt_val[i] > dr[i]) {
                ult_dist = 0;
            } else {
                ult_dist = min(ult_dist, (dr[i] - nxt_val[i]) * 2);
            }
        }
        if (special == i) {
            ult_dist = 0;
        }
        v[i]--;
        while (v[i] && sum <= i - 1) {
            sum += dist;
            v[i]--;
            dists[dist]++;
        }
        if (v[i]) {
            dists[dist] += v[i];
            sum += v[i] * dist;
            while (dists.size() && sum > i - 1) {
                auto [x, y] = *dists.rbegin();
                if (sum - x * y > i - 1) {
                    dists.erase(x);
                    sum -= x * y;
                } else {
                    int dif = sum - (i - 1);
                    int scot = (dif - 1) / x;
                    sum -= scot * x;
                    dists[x] -= scot;
                    if (!dists[x]) {
                        dists.erase(x);
                    }
                    break;
                }
            }
        }
        if (sum > i - 1) {
            auto [x, y] = *dists.rbegin();
            if (x >= ult_dist) {
                dists[x]--;
                if (!dists[x]) {
                    dists.erase(x);
                }
                sum -= x;
            }
        }
        if (sum <= i - 1) {
            sum += ult_dist;
            dists[ult_dist]++;
        }
    }
    for (auto it : dists) {
        ans -= it.second;
    }
    cout << ans;
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 25 / 25
• Subtask 5: 27 / 27