제출 #832150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832150		vjudge1	Feast (NOI19_feast)	C++17	30 / 100	121 ms	37536 KiB

feast

#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 / 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