Submission #328434

#	Time	Username	Problem	Language	Result	Execution time	Memory
328434		ryangohca	Feast (NOI19_feast)	C++17	100 / 100	490 ms	22380 KiB

feast

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define pii pair<int, int>
set<pii> nums;
set<pii> absnums;
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    bool ispos = true;
    bool acceptneg = false;
    int s = 0;
    int idx = 0;
    for (int i = 0; i < n; i++){
        int g; cin >> g;
        if (g > 0) {
            acceptneg = true;
            if (!ispos){
                nums.insert({idx, s});
                absnums.insert({llabs(s), idx});
                s = 0;
                ispos = true;
                idx++;
            }
            s += g;
        } else {
            if (!acceptneg) continue;
            if (ispos){
                nums.insert({idx, s});
                absnums.insert({llabs(s), idx});
                s = 0;
                ispos = false;
                idx++;
            }
            s += g;
        }
    }
    if (s > 0){
        nums.insert({idx, s});
        absnums.insert({s, idx});
    }
    while (nums.size() / 2 + 1 > k){
        auto [s, idx] = *absnums.begin(); absnums.erase(absnums.begin());
        auto itr = nums.lower_bound({idx - 1, 1e18});
        auto [curridx, val] = *itr;
        itr++;
        if (itr != nums.end()){
            auto [idx, nval] = *itr;
            val += nval;
            itr--;
            absnums.erase({llabs(nval), idx});
            nums.erase({idx, nval});
        } else {
            itr--;
        }
        if (itr != nums.begin()){
            itr--;
            auto [idx, pval] = *itr;
            val += pval;
            itr++;
            absnums.erase({llabs(pval), idx});
            nums.erase({idx, pval});
        }
        nums.erase(itr);
        nums.insert({curridx, val});
        if (val <= 0){
            auto itr = nums.find({curridx, val});
            if (itr == nums.begin()){
                nums.erase(itr);
            } else if ((++itr) == nums.end()){
                --itr;
                nums.erase(itr);
            } else {
                absnums.insert({llabs(val), curridx});
            }
        } else {
            absnums.insert({llabs(val), curridx});
        }
    }
    int ans = 0;
    for (auto [idx, num] : nums){
        if (num > 0) ans += num;
    }
    cout << ans << '\n';
}

Compilation message (stderr)

feast.cpp: In function 'int32_t main()':
feast.cpp:42:32: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   42 |     while (nums.size() / 2 + 1 > k){
      |            ~~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29