oj.uz

Submission #832148

# Submission time Handle Problem Language Result Execution time Memory
832148 2023-08-21T03:34:47 Z vjudge1 Feast (NOI19_feast) C++17
4 / 100
 103 ms 17884 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=-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 86 ms 17740 KB Output is correct
2 Correct 89 ms 17756 KB Output is correct
3 Correct 103 ms 17872 KB Output is correct
4 Correct 87 ms 17824 KB Output is correct
5 Correct 88 ms 17864 KB Output is correct
6 Correct 86 ms 17784 KB Output is correct
7 Correct 89 ms 17812 KB Output is correct
8 Correct 89 ms 17868 KB Output is correct
9 Correct 87 ms 17752 KB Output is correct
10 Correct 86 ms 17788 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17816 KB Output is correct
2 Correct 50 ms 17884 KB Output is correct
3 Correct 49 ms 17804 KB Output is correct
4 Correct 50 ms 17804 KB Output is correct
5 Incorrect 86 ms 17764 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 17856 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 17740 KB Output is correct
2 Correct 89 ms 17756 KB Output is correct
3 Correct 103 ms 17872 KB Output is correct
4 Correct 87 ms 17824 KB Output is correct
5 Correct 88 ms 17864 KB Output is correct
6 Correct 86 ms 17784 KB Output is correct
7 Correct 89 ms 17812 KB Output is correct
8 Correct 89 ms 17868 KB Output is correct
9 Correct 87 ms 17752 KB Output is correct
10 Correct 86 ms 17788 KB Output is correct
11 Correct 48 ms 17816 KB Output is correct
12 Correct 50 ms 17884 KB Output is correct
13 Correct 49 ms 17804 KB Output is correct
14 Correct 50 ms 17804 KB Output is correct
15 Incorrect 86 ms 17764 KB Output isn't correct
16 Halted 0 ms 0 KB -