oj.uz

Submission #328427

# Submission time Handle Problem Language Result Execution time Memory
328427 2020-11-16T14:17:14 Z ryangohca Feast (NOI19_feast) C++17
4 / 100
 497 ms 40940 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define pii pair<int, int>
set<pii> nums;
set<pii> absnums;
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({abs(s), idx});
                s = 0;
                ispos = true;
                idx++;
            }
            s += g;
        } else {
            if (!acceptneg) continue;
            if (ispos){
                nums.insert({idx, s});
                absnums.insert({abs(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({abs(nval), idx});
            nums.erase({idx, nval});
        }
        if (itr != nums.begin()){
            itr--;
            auto [idx, pval] = *itr;
            val += pval;
            itr++;
            absnums.erase({abs(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({abs(val), curridx});
            }
        } else {
            absnums.insert({abs(val), curridx});
        }
    }
    int ans = 0;
    for (auto [idx, num] : nums){
        if (num > 0) ans += num;
    }
    cout << ans << '\n';
}

Compilation message

feast.cpp:7:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 | main() {
      |      ^
feast.cpp: In function 'int 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 3180 KB Output is correct
2 Correct 39 ms 3180 KB Output is correct
3 Correct 35 ms 3180 KB Output is correct
4 Correct 35 ms 3180 KB Output is correct
5 Correct 35 ms 3308 KB Output is correct
6 Correct 33 ms 3180 KB Output is correct
7 Correct 41 ms 3180 KB Output is correct
8 Correct 35 ms 3180 KB Output is correct
9 Correct 34 ms 3308 KB Output is correct
10 Correct 34 ms 3200 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1528 KB Output is correct
2 Correct 24 ms 1516 KB Output is correct
3 Runtime error 24 ms 1772 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 497 ms 40940 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 620 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 620 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 620 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 3180 KB Output is correct
2 Correct 39 ms 3180 KB Output is correct
3 Correct 35 ms 3180 KB Output is correct
4 Correct 35 ms 3180 KB Output is correct
5 Correct 35 ms 3308 KB Output is correct
6 Correct 33 ms 3180 KB Output is correct
7 Correct 41 ms 3180 KB Output is correct
8 Correct 35 ms 3180 KB Output is correct
9 Correct 34 ms 3308 KB Output is correct
10 Correct 34 ms 3200 KB Output is correct
11 Correct 23 ms 1528 KB Output is correct
12 Correct 24 ms 1516 KB Output is correct
13 Runtime error 24 ms 1772 KB Execution killed with signal 6 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -