Submission #1207597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207597		Newtonabc	Feast (NOI19_feast)	C++20	100 / 100	137 ms	12176 KiB

feast

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
long long arr[N];
pair<long long,int> dp[N][2];
int n;
pair<long long,int> cal(long long lamb){
    dp[0][0]={0,0};
    dp[0][1]={-1e18,0};
    for(int i=1;i<=n;i++) dp[i][1]={-1e18,0},dp[i][0]={0,0};
    for(int i=1;i<=n;i++){
        dp[i][0]=max(dp[i][0],dp[i-1][0]);
        dp[i][0]=max(dp[i][0],dp[i-1][1]);
        dp[i][1]=max(dp[i][1],{dp[i-1][0].first+arr[i]-lamb,dp[i-1][0].second+1});
        dp[i][1]=max(dp[i][1],{dp[i-1][1].first+arr[i],dp[i-1][1].second});
    }
    return max(dp[n][0],dp[n][1]);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int k;
    cin>>n >>k;
    for(int i=1;i<=n;i++) cin>>arr[i];
    long long l=0,r=3e14,ans;
    while(l<r){
        long long mid=(l+r+1LL)/2LL;
        auto [a,b]=cal(mid);
        if(b>=k) l=mid;
        else r=mid-1LL;
    }
    auto [tmpa,tmpb]=cal(l);
    ans=tmpa+l*k;
    cout<<ans;
}

• 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