Submission #1230218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230218		pumkinhead	Feast (NOI19_feast)	C++20	100 / 100	86 ms	17580 KiB

feast

#include <bits/stdc++.h>
using namespace std;
template<typename T> struct LinkedList;
void attemptMergeNext(LinkedList<long long>& list, int ind);
template<typename T> struct LinkedList{
    int frontInd = -1;
    int backInd = -1;
    struct Node{
        int next = -1;
        int prev = -1;
        int version = 0;
        T val;
        Node(){}
        Node(T val){
            this->val = val;
        }
    };
    vector<Node> nodes;
    void erase(int ind){
        nodes[ind].version++;
        if(nodes[ind].next != -1){
            nodes[nodes[ind].next].prev = nodes[ind].prev;
        }
        if(nodes[ind].prev != -1){
            nodes[nodes[ind].prev].next = nodes[ind].next;
        }
        if(frontInd == ind){
            frontInd = nodes[ind].next;
        }
        if(backInd == ind){
            backInd = nodes[ind].prev;
        }
        // if(nodes[ind].prev != -1){
        //     attemptMergeNext(*this, nodes[ind].prev);
        // }
    }
    void merge(int ind){
        nodes[ind].version++;
        if(nodes[ind].next != -1){
            nodes[ind].val += nodes[nodes[ind].next].val;
            erase(nodes[ind].next);
        }
        if(nodes[ind].prev != -1){
            nodes[ind].val += nodes[nodes[ind].prev].val;
            erase(nodes[ind].prev);
        }
    }
    void append(T val){
        Node node = Node(val);
        int ind = nodes.size();
        if(backInd == -1){
            frontInd = ind;
        }else{
            nodes[backInd].next = ind;
            node.prev = backInd;
        }
        int prevInd = backInd;
        backInd = ind;
        nodes.push_back(node);
        if(prevInd == -1) return;
        bool shouldMerge = (nodes[ind].val == 0 || nodes[prevInd].val == 0 || (!((nodes[ind].val > 0) ^ (nodes[prevInd].val > 0))));
        if(!shouldMerge) return;
        merge(ind);
    }
    T& front(){
        return nodes[frontInd].val;
    }
    T& back(){
        return nodes[backInd].val;
    }
    Node get(int ind){
        return nodes[ind];
    }
};
void attemptMergeNext(LinkedList<long long>& list, int ind){
    // int nextInd = list.nodes[ind].next;
    // if(nextInd == -1) return;
    // bool merge = (list.nodes[ind].val == 0 || list.nodes[nextInd].val == 0 || (!((list.nodes[ind].val > 0) ^ (list.nodes[nextInd].val > 0))));
    // if(merge){
    //     list.mergeNext(ind);
    // }
}
long long greedySolve(int n, int k, vector<int> inp){
    vector<int> a;
    for(int i=0; i<n; i++){
        if(inp[i] == 0) continue;
        a.push_back(inp[i]);
    }
    if(a.empty()) return 0;
    n = a.size();
    LinkedList<long long> segments;
    segments.append(a.front());
    for(int i=1; i<n; i++){
        segments.append(a[i]);
    }
    if(segments.front() < 0){
        segments.erase(segments.frontInd);
    }
    if(segments.frontInd == -1) return 0;
    if(segments.back() < 0){
        segments.erase(segments.backInd);
    }
    if(segments.backInd == -1) return 0;
    long long ans = 0;
    int segCount = 0;
    priority_queue<pair<long long, pair<int, int>>> elemsToErase;
    int ind = segments.frontInd;
    while(ind != -1){
        long long val = segments.get(ind).val;
        elemsToErase.push({-abs(val), {ind, segments.get(ind).version}});
        if(val > 0){
            ans += val;
            segCount++;
        }
        ind = segments.get(ind).next;
    }
    while(segCount > k){
        pair<long long, pair<int, int>> elem = elemsToErase.top();
        elemsToErase.pop();
        int node = elem.second.first;
        if(segments.get(node).version != elem.second.second) continue;
        long long val = segments.get(node).val;
        ans -= abs(val);
        bool erase = segments.backInd == node || node == segments.frontInd;
        segments.merge(node);
        if(erase){
            segments.erase(node);
        }else{
            elemsToErase.push({-abs(segments.get(node).val), {node, segments.get(node).version}});
        }
        segCount--;
    }
    return ans;
}
long long dpSolve(int n, int k, vector<int> a){
    vector<vector<long long>> dp[2];
    for(int i=0; i<2; i++){
        dp[i] = vector<vector<long long>>(n, vector<long long>(k + 1, 0));
    }
    dp[1][0][1] = max(0, a[0]);
    for(int i=1; i<n; i++){
        for(int j=1; j<=k; j++){
            dp[0][i][j] = max({dp[0][i][j], dp[0][i-1][j], dp[1][i-1][j]});
            dp[1][i][j] = max({dp[1][i][j], dp[0][i-1][j-1] + a[i], dp[1][i-1][j] + a[i]});
        }
    }
    long long bestAns = 0;
    for(int i=1; i<=k; i++){
        for(int j=0; j<2; j++){
            bestAns = max(bestAns, dp[j][n-1][i]);
        }
    }
    return bestAns;
}
void bruteforce(int t){
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int successes = 0;
    for(int j=0; j<t; j++){
        uniform_int_distribution<int> nDist(1, 10);
        int n = nDist(rng);
        uniform_int_distribution<int> kDist(1, n);
        int k = kDist(rng);
        vector<int> a(n);
        uniform_int_distribution<int> aDist(-10, 10);
        for(int i=0; i<n; i++){
            a[i] = aDist(rng);
        }
        int greedyAns = greedySolve(n, k, a);
        int dpAns = dpSolve(n, k, a);
        if(greedyAns != dpAns){
            cout<<"MISMATCH FOUND!\n"<<n<<" "<<k<<"\n";
            for(int i=0; i<n; i++){
                cout<<a[i]<<" ";
            }
            cout<<"\nExpected: "<<dpAns<<"\nFound: "<<greedyAns<<"\n"<<endl;
        }else{
            successes++;
        }
    }
    double accuracy = (double) successes / t * 100;
    cout<<accuracy<<"% accuracy";
}
int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    if(false){
        bruteforce(10000);
    }
    int n, k;
    cin>>n>>k;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    // if(n <= 2000 || k == 1){
    //     cout<<dpSolve(n, k, a);
    // }else{
        cout<<greedySolve(n, k, a);
    // }
}
/*
3 1
2 -1 3
*/
/*

*/

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