Submission #1229297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229297		pumkinhead	Feast (NOI19_feast)	C++20	53 / 100	46 ms	51528 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 mergeNext(int ind){
        assert(nodes[ind].next != -1);
        nodes[ind].val += nodes[nodes[ind].next].val;
        nodes[ind].version++;
        erase(nodes[ind].next);
    }
    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;
        }
        backInd = ind;
        nodes.push_back(node);
        if(node.prev != -1){
            attemptMergeNext(*this, node.prev);
        }
    }
    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;
        if(val < 0){
            elemsToErase.push({val, {ind, segments.get(ind).version}});
        }else{
            ans += val;
            segCount++;
            elemsToErase.push({-val, {ind, segments.get(ind).version}});
        }
        if(segCount > k){
            while(true){
                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;
                if(val > 0){
                    ans -= val;
                    if(segments.get(node).prev != -1){
                        node = segments.get(node).prev;
                        segments.mergeNext(node);
                    }
                    if(segments.get(node).next != -1){
                        segments.mergeNext(node);
                    }
                    elemsToErase.push({segments.get(node).val, {node, segments.get(node).version}});
                }else{
                    ans += val;
                    segments.erase(node);
                    if(segments.get(node).prev != -1){
                        node = segments.get(node).prev;
                    }else{
                        node = segments.frontInd;
                    }
                    elemsToErase.push({segments.get(node).val, {node, segments.get(node).version}});
                }
                break;
            }
            segCount--;
        }
        ind = segments.get(ind).next;
    }
    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;
}
int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    int n, k;
    cin>>n>>k;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    if(n <= 2000){
        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: 0 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 0 / 29