oj.uz

Submission #832150

# Submission time Handle Problem Language Result Execution time Memory
832150 2023-08-21T03:41:57 Z vjudge1 Feast (NOI19_feast) C++17
30 / 100
 121 ms 37536 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax = 3e5+5;
int A[nmax];
struct allin {
    long long sum;
    long long maxsum;
    long long preff;
    long long suff;
};
allin segtree[4*nmax];
void build(int idx, int low, int high) {
    if(low==high) {
        segtree[idx].sum = A[low];
        segtree[idx].maxsum = A[low];
        segtree[idx].preff = A[low];
        segtree[idx].suff = A[low];
        return;
    }
    int mid = (low+high)/2;
    build(2*idx,low,mid);
    build(2*idx+1,mid+1,high);
    segtree[idx].sum = segtree[2*idx].sum + segtree[2*idx+1].sum;
    segtree[idx].maxsum = max(max(segtree[2*idx].maxsum, segtree[2*idx+1].maxsum), segtree[2*idx].suff + segtree[2*idx+1].preff);
    segtree[idx].preff = max(segtree[2*idx].preff, segtree[2*idx].sum + segtree[2*idx+1].preff);
    segtree[idx].suff = max(segtree[2*idx+1].suff, segtree[2*idx+1].sum + segtree[2*idx].suff);
}
allin query(int idx, int low, int high, int l, int r) {
    if(low>=l && high<=r) {
        return segtree[idx];
    }
    int mid = (low+high)/2;
    if(r<=mid) {
        return query(2*idx, low, mid, l, r);
    } else
    if(l>mid) {
        return query(2*idx+1, mid+1, high, l, r);
    } else {
        allin left = query(2*idx, low, mid, l, r);
        allin right = query(2*idx+1, mid+1, high, l, r);
        allin merge;
        merge.sum = left.sum + right.sum;
        merge.maxsum = max(max(left.maxsum, right.maxsum), left.suff+right.preff);
        merge.preff = max(left.preff, left.sum+right.preff);
        merge.suff = max(right.suff, right.sum+left.suff);
        return merge;
    }
}
int main() {
    int N,K;
    cin >> N >> K;
    bool subs1 = true;
    long long summ=0;
    for(int i=1; i<=N; i++) {
        cin >> A[i];
        if(A[i]<0) subs1=false;
        summ+=A[i];
    }
    build(1,1,N);
    if(subs1) {
        cout << summ << endl;
        return 0;
    }
    if(K==1) {
        allin ans = query(1,1,N,1,N);
        cout << ans.maxsum << endl;
        return 0;
    }
    int posneg=-1;
    for(int i=1; i<=N; i++) {
        if(A[i]<0) {
            posneg = i;
            break;
        }
    }
    summ=0;
    if(K>=2 && posneg!=-1) {
        for(int i=1; i<posneg; i++) {
            summ+=A[i];
        }
        for(int i=posneg+1; i<=N; i++) {
            summ+=A[i];
        }
        cout << summ << endl;
        return 0;
    }
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 35788 KB Output is correct
2 Correct 96 ms 35788 KB Output is correct
3 Correct 96 ms 35716 KB Output is correct
4 Correct 97 ms 35896 KB Output is correct
5 Correct 95 ms 35728 KB Output is correct
6 Correct 121 ms 35788 KB Output is correct
7 Correct 93 ms 35764 KB Output is correct
8 Correct 98 ms 35824 KB Output is correct
9 Correct 101 ms 35788 KB Output is correct
10 Correct 94 ms 35796 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 35276 KB Output is correct
2 Correct 57 ms 35428 KB Output is correct
3 Correct 56 ms 35276 KB Output is correct
4 Correct 57 ms 35412 KB Output is correct
5 Correct 94 ms 35768 KB Output is correct
6 Correct 55 ms 35300 KB Output is correct
7 Correct 57 ms 35364 KB Output is correct
8 Correct 94 ms 37156 KB Output is correct
9 Correct 92 ms 37028 KB Output is correct
10 Correct 57 ms 35404 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 35792 KB Output is correct
2 Correct 99 ms 37224 KB Output is correct
3 Correct 99 ms 37268 KB Output is correct
4 Correct 99 ms 37240 KB Output is correct
5 Correct 112 ms 37224 KB Output is correct
6 Correct 103 ms 37216 KB Output is correct
7 Correct 102 ms 37228 KB Output is correct
8 Correct 101 ms 37264 KB Output is correct
9 Correct 101 ms 37324 KB Output is correct
10 Correct 107 ms 37536 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 35788 KB Output is correct
2 Correct 96 ms 35788 KB Output is correct
3 Correct 96 ms 35716 KB Output is correct
4 Correct 97 ms 35896 KB Output is correct
5 Correct 95 ms 35728 KB Output is correct
6 Correct 121 ms 35788 KB Output is correct
7 Correct 93 ms 35764 KB Output is correct
8 Correct 98 ms 35824 KB Output is correct
9 Correct 101 ms 35788 KB Output is correct
10 Correct 94 ms 35796 KB Output is correct
11 Correct 56 ms 35276 KB Output is correct
12 Correct 57 ms 35428 KB Output is correct
13 Correct 56 ms 35276 KB Output is correct
14 Correct 57 ms 35412 KB Output is correct
15 Correct 94 ms 35768 KB Output is correct
16 Correct 55 ms 35300 KB Output is correct
17 Correct 57 ms 35364 KB Output is correct
18 Correct 94 ms 37156 KB Output is correct
19 Correct 92 ms 37028 KB Output is correct
20 Correct 57 ms 35404 KB Output is correct
21 Correct 101 ms 35792 KB Output is correct
22 Correct 99 ms 37224 KB Output is correct
23 Correct 99 ms 37268 KB Output is correct
24 Correct 99 ms 37240 KB Output is correct
25 Correct 112 ms 37224 KB Output is correct
26 Correct 103 ms 37216 KB Output is correct
27 Correct 102 ms 37228 KB Output is correct
28 Correct 101 ms 37264 KB Output is correct
29 Correct 101 ms 37324 KB Output is correct
30 Correct 107 ms 37536 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Incorrect 2 ms 212 KB Output isn't correct
33 Halted 0 ms 0 KB -