Submission #1294654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294654		MisterReaper	Tortoise (CEOI21_tortoise)	C++20	8 / 100	2 ms	584 KiB

tortoise

// File A.cpp created on 24.11.2025 at 14:47:41
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    std::vector<int> disl(N, N), disr(N, N);
    for (int i = 0; i < N; ++i) {
        if (A[i] == -1) {
            disl[i] = 0;
            disr[i] = 0;
        }
    }
    for (int i = 1; i < N; ++i) {
        disl[i] = std::min(disl[i], disl[i - 1] + 1);
    }
    for (int i = N - 1; i >= 1; --i) {
        disr[i - 1] = std::min(disr[i - 1], disr[i] + 1);
    }

    debug(disl, disr);

    std::vector<int> p;
    std::vector<int> ord;
    p.reserve(N);
    ord.reserve(N);
    for (int i = 0; i < N; ++i) {
        if (A[i] >= 0) {
            ord.emplace_back(i);
        } else {
            p.emplace_back(i);
        }
    }
    std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) -> bool {
        return std::min(disl[lhs], disr[lhs]) < std::min(disl[rhs], disr[rhs]);
    });

    int n = int(p.size());

    std::vector<int> cnt(N);
    auto check = [&]() -> bool {
        debug(cnt);
        auto c = cnt;
        int now = 0;
        for (int j = 0; j <= n; ++j) {
            int l = (j == 0 ? 0 : p[j - 1] + 1);
            int r = (j == n ? N : p[j]);
            int first = -1;
            for (int i = r - 1; i >= l; --i) {
                if (c[i] > 0) {
                    first = i;
                    c[i] -= 1;
                    break;
                }
            }
            if (first == -1) {
                continue;
            }
            for (int i = l; i < r; ++i) {
                if (c[i] == 0) {
                    continue;
                }
                while (c[i] > 1) {
                    debug(i, now);
                    if (now > i) {
                        return false;
                    }
                    now += std::min(disl[i], disr[i]) * 2;
                    c[i]--;
                }
                debug(i, now);
                if (now > i) {
                    return false;
                }
                int next = i + 1;
                while (next < first && c[next] <= 0) {
                    next++;
                }
                now += std::min(disl[i] * 2, (disr[i] - next + i) * 2);
            }
            debug(now, first);
            if (now > first) {
                return false;
            }
        }
        return true;
    };

    int ans = 0;
    for (auto i : ord) {
        while (cnt[i] < A[i]) {
            cnt[i] += 1;
            if (!check()) {
                cnt[i] -= 1;
                break;
            }
            ans += 1;
            debug(cnt);
        }
    }

    debug(ans);

    i64 total = 0;
    for (int i = 0; i < N; ++i) {
        total += std::max(0, A[i]);
    }

    std::cout << total - ans << '\n';

    return 0;
}

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