Submission #833139

#	Time	Username	Problem	Language	Result	Execution time	Memory
833139		isaachew	Feast (NOI19_feast)	C++17	59 / 100	1090 ms	11000 KiB

feast

#include <bits/stdc++.h>
/*
 
 */
int main(){
    int n,k;
    std::cin>>n>>k;
    std::vector<int> nums;
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        nums.push_back(x);
    }
    std::vector<long long> seg(n+1);//segment active
    std::vector<long long> noseg(n+1);//no segment active
    for(int i=0;i<k;i++){
        std::vector<long long> seg2(n+1);
        std::vector<long long> noseg2(n+1);
        for(int j=1;j<n+1;j++){
            seg2[j]=std::max(noseg[j],seg2[j-1]+nums[j-1]);
            noseg2[j]=std::max(seg2[j],noseg2[j-1]);
        }
        seg=seg2,noseg=noseg2;
    }
    std::cout<<noseg[n]<<'\n';
}

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