Submission #1358954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1358954		Newtonabc	Feast (NOI19_feast)	C++20	18 / 100	105 ms	12156 KiB

feast

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

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