Submission #1017575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017575		ara_ara	Feast (NOI19_feast)	C++17	100 / 100	136 ms	12172 KiB

feast

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
const int maxn=3e5+5;
int n,k;
int a[maxn];
pair<int,int> alien(int lambda){
    pair<int,int> dp[n+5][2]={};
    dp[0][1].first=-inf;
    for(int i=1;i<=n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        pair<int,int> p1={dp[i-1][0].first+a[i]-lambda,dp[i-1][0].second+1};
        pair<int,int> p2={dp[i-1][1].first+a[i],dp[i-1][1].second};
        dp[i][1]=max(p1,p2);
    }
    return max(dp[n][1],dp[n][0]);
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=0,r=inf;
    while(l<r){
        int lambda=(l+r+1)>>1;
        pair<int,int> tmp=alien(lambda);
        if(tmp.second>=k) l=lambda;
        else r=lambda-1;
    }
    cout<<alien(l).first+k*l;
}

• 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