Submission #1017560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017560		vjudge1	Feast (NOI19_feast)	C++17	100 / 100	956 ms	24172 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define int long long
pair<int,int> solve(int l,int a[],int n){
    vector<vector<pair<int,int>>> DP(n,vector<pair<int,int>>(2));
    DP[0][0]={0,0};
    DP[0][1]={a[0]-l,1};
    for(int i=1;i<n;i++){
        DP[i][0]=max(DP[i-1][0],DP[i-1][1]);
        DP[i][1]=max(DP[i-1][1],{DP[i-1][0].first-l,DP[i-1][0].second+1});
        DP[i][1].first+=a[i];
    }
    return max(DP[n-1][0],DP[n-1][1]);
}
signed main() {
    int n,k;
    cin >> n >> k;
    int a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    int low=0,high=1e18;
    low--,high++;
    while(high-low>1){
        int mid=(high-low)/2+low;
        if(solve(mid,a,n).second>=k){
            low=mid;
        }
        else{
            high=mid;
        }
    }
    if(low==-1){
        low++;
    }
    cout << solve(low,a,n).first+low*k;
}

• 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