Submission #225056

#	Time	Username	Problem	Language	Result	Execution time	Memory
225056		tictaccat	Feast (NOI19_feast)	C++14	30 / 100	254 ms	13672 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define int long long

int N,K;
int A[500000], v[500000], l[500000], r[500000], a[500000];
priority_queue<pair<int,int>> pq;
// priority_queue<pair<int,int>> pq;

main() {

    cin >> N >> K;

    int cur = 0, t = 0, pos = 0;
    for (int i = 0; i <= N; i++) {
        if (i < N) cin >> A[i];
        if (i < N && (cur >= 0) == (A[i] >= 0)) cur += A[i];
        else {
            if (cur == 0) {
                cur = A[i];
                continue;
            }
          //  cout << i << " " << cur << " " << t << "\n";
            v[t] = cur;
            l[t] = t-1;
            r[t] = t+1;
            pq.push(make_pair(-abs(cur),t));
            a[t] = 1;
            t++; 
            if (cur > 0) pos++;
            cur = A[i];
        }
    }

    int x = 0, ans = 0;

    //cout << "\n";
    
    while (!pq.empty()) {
        int val, i;
        tie(val, i) = pq.top();
        pq.pop();
        if (!a[i]) continue;
        if (pos > K) {
            //cout << "a " << v[i] << " " << i << "\n";
            if (v[i] > 0) pos--;
            if (l[i] != -1) {
                if (v[l[i]] > 0) pos--;
                v[i] += v[l[i]];
                r[l[l[i]]] = i;
                a[l[i]] = 0;
                l[i] = l[l[i]];
            }
            if (r[i] != t) {
                if (v[r[i]] > 0) pos--;
                v[i] += v[r[i]];
                l[r[r[i]]] = i;
                a[r[i]] = 0;
                r[i] = r[r[i]];
            }
            pq.push(make_pair(-abs(v[i]),i));
           // cout << "add " << v[i] << " " << i << " " << a[i] << "\n";
            if (v[i] > 0) pos++;
        }
        else {
          //  cout << "b " << v[i] << " " << i << " " << a[i] << "\n";
            if (v[i] > 0) {
                ans += v[i];
              //  cout << "! " << v[i] << "\n";
            }
        }
        //cout << v[i] << " " << i << "\n";

        //if (++x == 3) break;
    }

    cout << ans << "\n";

    //cout <<  pos << "\n";

}

Compilation message (stderr)

feast.cpp:10:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
feast.cpp: In function 'int main()':
feast.cpp:35:9: warning: unused variable 'x' [-Wunused-variable]
     int x = 0, ans = 0;
         ^

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