oj.uz

Submission #330349

# Submission time Handle Problem Language Result Execution time Memory
330349 2020-11-24T20:49:49 Z jungsnow Feast (NOI19_feast) C++14
4 / 100
 1000 ms 13036 KB 
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;
using ll = long long;

const int maxn = 500100;

typedef pair<ll, int> ii;

int N, M, K;
ll A[maxn], L[maxn], R[maxn];
set<ii> s;

int main() {
//    freopen("feast.inp", "r", stdin);
//    freopen("feast.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> K;
    while (N--) {
        int V; cin >> V;
        if (M == 0) {
            if (V > 0) A[++M] = V;
            continue;
        }
        if ((A[M] > 0) == (V > 0)) A[M] += V;
        else A[++M] = V;
    }
    if (A[M] < 0) {
        A[M] = 0;
        --M;
    }
    int Cn = 0;
    for (int i = 1; i <= M; ++i) {
        Cn += (A[i] > 0);
        L[i] = i - 1; R[i] = i + 1;
        s.insert(ii(abs(A[i]), i));
    }
    R[M] = 0;
    while (Cn > K) {
        ii Cur = *s.begin(); s.erase(Cur);
        int i = Cur.y;
        ll Val = A[i], LL = L[i], RR = R[i];
        if (A[i] > 0) Cn--;
        if (LL) {
            if (A[LL] > 0) Cn--;
            s.erase(ii(A[LL], LL));
            Val += A[LL];
            if (L[LL]) R[L[LL]] = i;
        }
        if (RR) {
            if (A[RR] > 0) Cn--;
            s.erase(ii(A[RR], RR));
            Val += A[RR];
            if (R[RR]) L[R[RR]] = i;
        }
        A[i] = Val;
        A[LL] = A[RR] = 0;
        if (L[i] == 0 && A[i] < 0) {
            L[R[i]] = 0;
            A[i] = 0;
        } else if (R[i] == 0 && A[i] < 0) {
            R[L[i]] = 0;
            A[i] = 0;
        } else s.insert(ii(abs(A[i]), i));
        Cn += (A[i] > 0);
    }
    ll Ans = 0;
    for (auto i : s) {
        Ans += max(A[i.y], 0ll);
    }
    cout << Ans << '\n';
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 13036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 364 KB Output is correct
2 Correct 34 ms 364 KB Output is correct
3 Correct 34 ms 364 KB Output is correct
4 Correct 34 ms 364 KB Output is correct
5 Correct 41 ms 364 KB Output is correct
6 Correct 34 ms 492 KB Output is correct
7 Correct 33 ms 364 KB Output is correct
8 Correct 33 ms 364 KB Output is correct
9 Correct 40 ms 364 KB Output is correct
10 Correct 41 ms 364 KB Output is correct
11 Execution timed out 1094 ms 364 KB Time limit exceeded
12 Halted 0 ms 0 KB -