Submission #1173404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173404		hamzabc	Feast (NOI19_feast)	C++20	0 / 100	98 ms	27864 KiB

feast

#include <bits/stdc++.h>

using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'


vector<long long> feast;


class divandqonqtree{
private:
    divandqonqtree *lfttree, *rgttree;
    struct prefixdata{
        long long int maximumrightmostsum = 0;
        int leftind = 0;
        long long int maximumsubarraysum = 0;
        int kanadeleft = 0;
        int kanaderight = 0;
    };
    struct sufixdata{
        long long int maximumleftmostsum = 0;
        int rightind = 0;
        long long int maximumsubarraysum = 0;
        int kanadeleft = 0;
        int kanaderight = 0;
    };
    vector<prefixdata> prefix;
    vector<sufixdata> sufix;
    int l, m, r;
    long long deg;
public:
    void init(int gl, int gr){
        l = gl;
        r = gr;
        m = (l + r) >> 1;
        if (gl == gr){
            deg = feast[l];
            return;
        }
        if (l < m){
            lfttree = new divandqonqtree;
            lfttree->init(l, m - 1);
        }
        if (m < r){
            rgttree = new divandqonqtree;
            rgttree->init(m + 1, r);
        }
        long long int sum = 0, kanade = 0, kl = m;
        prefix.resize(m - l + 1);
        sufix.resize(r - m + 1);
        for (int i = m; i <= r; i++){
            sum += feast[i];
            kanade += feast[i];
            if (kanade < 0){
                kanade = 0;
                kl = i + 1;
            }
            if (i == m){
                sufix[0].maximumleftmostsum = max(0LL, sum);
                sufix[0].maximumsubarraysum = kanade;
                continue;
            }
            if (sufix[i - m - 1].maximumleftmostsum > sum){
                sufix[i - m].maximumleftmostsum = sufix[i - m - 1].maximumleftmostsum;
                sufix[i - m].rightind = sufix[i - m - 1].rightind;
            }else{
                sufix[i - m].maximumleftmostsum = sum;
                sufix[i - m].rightind = i;
            }
            if (sufix[i - m - 1].maximumsubarraysum > kanade){
                sufix[i - m].maximumsubarraysum = sufix[i - m - 1].maximumsubarraysum;
                sufix[i - m].kanadeleft = sufix[i - m - 1].kanadeleft;
                sufix[i - m].kanaderight = sufix[i - m - 1].kanaderight;
            }else{
                sufix[i - m].maximumsubarraysum = kanade;
                sufix[i - m].kanadeleft = kl;
                sufix[i - m].kanaderight = i;
            }
        }
        kl = m;
        sum = 0;
        kanade = 0;
        for (int i = m; i >= l; i--){
            if (i == m){
                prefix[0].maximumrightmostsum = sum;
                prefix[0].maximumsubarraysum = kanade;
                continue;
            }
            sum += feast[i];
            kanade += feast[i];
            if (kanade < 0){
                kanade = 0;
                kl = i - 1;
            }
            if (prefix[m - i - 1].maximumrightmostsum > sum){
                prefix[m - i].maximumrightmostsum = prefix[m - i - 1].maximumrightmostsum;
                prefix[m - i].leftind = prefix[m - i - 1].leftind;
            }else{
                prefix[m - i].maximumrightmostsum = sum;
                prefix[m - i].leftind = i;
            }
            if (prefix[m - i - 1].maximumsubarraysum > kanade){
                prefix[m - i].maximumsubarraysum = prefix[m - i - 1].maximumsubarraysum;
                prefix[m - i].kanadeleft = prefix[m - i - 1].kanadeleft;
                prefix[m - i].kanaderight = prefix[m - i - 1].kanaderight;
            }else{
                prefix[m - i].maximumsubarraysum = kanade;
                prefix[m - i].kanadeleft = i;
                prefix[m - i].kanaderight = kl;
            }
        }
    };

    array<long long, 3> query(int ql, int qr){
        if (ql > qr)
            return { -1, -1, -1 };
        if (qr < m){
            return lfttree->query(ql, qr);
        }
        if (ql > m){
            return rgttree->query(ql, qr);
        }
        if (l == r){
            return { deg, l, r };
        }
        long long mx = max(max(prefix[m - ql].maximumsubarraysum, sufix[qr - m].maximumsubarraysum), prefix[m - ql].maximumrightmostsum + sufix[qr - m].maximumleftmostsum);
        if (mx == prefix[m - ql].maximumsubarraysum)
            return { mx, prefix[m - ql].kanadeleft, prefix[m - ql].kanaderight };
        if (mx == sufix[qr - m].maximumsubarraysum)
            return { mx, sufix[qr - m].kanadeleft, sufix[qr - m].kanaderight };
        // if (mx == prefix[m - ql].maximumrightmostsum + sufix[qr - m].maximumleftmostsum)
        return { mx, prefix[m - ql].leftind, sufix[qr - m].rightind};
    }
};


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector<long long> original(N);
    multiset<long long> sm;
    for (int i = 0; i < N; i++){
        cin >> original[i];
        sm.insert(-original[i]);
    }
    long long int sum = 0;
    for (int o = 0; o < K; o++){
        if (*sm.begin() < 0)
            sum += -*sm.begin();
        sm.erase(sm.begin());
    }
    if (*sm.begin() >= 0){
        cout << sum;
        return 0;
    }
    for (int i = 0; i < N; i++){
        long long a = original[i];
        if (a == 0)
            continue;
        if (feast.size() == 0 && a > 0){
            feast.push_back(a);
            continue;
        }
        if (feast.back() * a > 0)
            feast.back() += a;
        else
            feast.push_back(a);
    }
    if (feast[feast.size() - 1] < 0)
        feast.pop_back();
    divandqonqtree normal, inverse;
    normal.init(0, feast.size() - 1);
    for (int i = 0; i < feast.size(); i++) feast[i] *= -1;
    inverse.init(0, feast.size() - 1);
    priority_queue<array<long long, 6>> prt;
    auto u = normal.query(0, feast.size() - 1);
    prt.push({ u[0], 0LL, (long long)feast.size() - 1LL, (long long)true, u[1], u[2] });
    long long int ret = 0;
    for (int i = 0; i < K; i++){
        auto fr = prt.top();
        prt.pop();
        ret += fr[0];
        if (fr[3]){
            u = normal.query(fr[1], fr[4] - 1);
            prt.push({ u[0], fr[0], fr[4] - 1, true, u[1], u[2] });
            u = normal.query(fr[5] + 1, fr[2]);
            prt.push({ u[0], fr[5] + 1, fr[1], true, u[1], u[2] });
            u = inverse.query(fr[4], fr[5]);
            prt.push({ u[0], fr[4], fr[5], false, u[1], u[2] });
        }else{
            u = inverse.query(fr[1], fr[4] - 1);
            prt.push({ u[0], fr[0], fr[4] - 1, false, u[1], u[2] });
            u = inverse.query(fr[5] + 1, fr[2]);
            prt.push({ u[0], fr[5] + 1, fr[1], false, u[1], u[2] });
            u = normal.query(fr[4], fr[5]);
            prt.push({ u[0], fr[4], fr[5], true, u[1], u[2] });
        }
    }
    cout << ret;
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29