제출 #1198441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198441		TheSahib	Bigger segments (IZhO19_segments)	C++20	100 / 100	77 ms	29676 KiB

segments

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n+1), S(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        S[i] = S[i-1] + a[i];
    }

    // k[i] = max number of segments covering [1..i]
    vector<int> k(n+1, 0);

    // min-heap for (T_j, j)
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> heapT;
    // max-heap for (k_j, S_j, j)
    priority_queue<tuple<int,ll,int>> heapK;

    // initialize j=0
    heapT.emplace(0LL, 0);
    k[0] = 0;

    for (int i = 1; i <= n; i++) {
        ll Si = S[i];
        // activate all j with T_j <= S_i
        while (!heapT.empty() && heapT.top().first <= Si) {
            auto [Tj, j] = heapT.top();
            heapT.pop();
            heapK.emplace(k[j], S[j], j);
        }
        
        // best previous j*
        auto [best_k, best_S, jstar] = heapK.top();
        k[i] = best_k + 1;
        // compute T_i = 2*S_i - S[j*]
        ll Ti = 2*Si - best_S;
        heapT.emplace(Ti, i);
    }

    cout << k[n] << "\n";
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27