oj.uz

Submission #832147

# Submission time Handle Problem Language Result Execution time Memory
832147 2023-08-21T03:29:58 Z vjudge1 Feast (NOI19_feast) C++17
4 / 100
 92 ms 21016 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax = 3e5+5;
int A[nmax];
struct allin {
    int sum;
    int maxsum;
    int preff;
    int 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;
    for(int i=1; i<=N; i++) {
        if(A[i]<0) {
            posneg = i;
            break;
        }
    }
    summ=0;
    if(K>=2) {
        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 86 ms 20584 KB Output is correct
2 Correct 87 ms 20688 KB Output is correct
3 Correct 91 ms 21016 KB Output is correct
4 Correct 86 ms 20704 KB Output is correct
5 Correct 87 ms 20628 KB Output is correct
6 Correct 85 ms 20612 KB Output is correct
7 Correct 85 ms 20604 KB Output is correct
8 Correct 86 ms 20696 KB Output is correct
9 Correct 87 ms 20632 KB Output is correct
10 Correct 85 ms 20680 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 18924 KB Output is correct
2 Correct 65 ms 18924 KB Output is correct
3 Correct 49 ms 18904 KB Output is correct
4 Correct 50 ms 18904 KB Output is correct
5 Incorrect 89 ms 20616 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 20844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 20584 KB Output is correct
2 Correct 87 ms 20688 KB Output is correct
3 Correct 91 ms 21016 KB Output is correct
4 Correct 86 ms 20704 KB Output is correct
5 Correct 87 ms 20628 KB Output is correct
6 Correct 85 ms 20612 KB Output is correct
7 Correct 85 ms 20604 KB Output is correct
8 Correct 86 ms 20696 KB Output is correct
9 Correct 87 ms 20632 KB Output is correct
10 Correct 85 ms 20680 KB Output is correct
11 Correct 49 ms 18924 KB Output is correct
12 Correct 65 ms 18924 KB Output is correct
13 Correct 49 ms 18904 KB Output is correct
14 Correct 50 ms 18904 KB Output is correct
15 Incorrect 89 ms 20616 KB Output isn't correct
16 Halted 0 ms 0 KB -