oj.uz

Submission #328429

# Submission time Handle Problem Language Result Execution time Memory
328429 2020-11-16T14:30:16 Z ryangohca Feast (NOI19_feast) C++17
4 / 100
 495 ms 38068 KB 
#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});
        }
        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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 492 KB Output is correct
2 Correct 33 ms 364 KB Output is correct
3 Correct 34 ms 364 KB Output is correct
4 Correct 33 ms 364 KB Output is correct
5 Correct 33 ms 364 KB Output is correct
6 Correct 32 ms 364 KB Output is correct
7 Correct 33 ms 364 KB Output is correct
8 Correct 40 ms 364 KB Output is correct
9 Correct 44 ms 364 KB Output is correct
10 Correct 43 ms 364 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 364 KB Output is correct
2 Correct 23 ms 364 KB Output is correct
3 Runtime error 23 ms 748 KB Execution killed with signal 6 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 495 ms 38068 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 492 KB Output is correct
2 Correct 33 ms 364 KB Output is correct
3 Correct 34 ms 364 KB Output is correct
4 Correct 33 ms 364 KB Output is correct
5 Correct 33 ms 364 KB Output is correct
6 Correct 32 ms 364 KB Output is correct
7 Correct 33 ms 364 KB Output is correct
8 Correct 40 ms 364 KB Output is correct
9 Correct 44 ms 364 KB Output is correct
10 Correct 43 ms 364 KB Output is correct
11 Correct 22 ms 364 KB Output is correct
12 Correct 23 ms 364 KB Output is correct
13 Runtime error 23 ms 748 KB Execution killed with signal 6 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -