Submission #727197

#	Time	Username	Problem	Language	Result	Execution time	Memory
727197		PenguinsAreCute	Feast (NOI19_feast)	C++17	100 / 100	220 ms	7464 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define stMx(a,b) a = max(a,b)
typedef pair<int,int> ii;
#define REP(i, a, b) for(int i = a; i < b; i++)
int32_t main() {
    int N, K; cin >> N >> K; int A[N+1]; A[0]=0;
    REP(i,1,N+1) {
        cin>>A[i];
        A[i]+=A[i-1];
    }
    ii dp[N+1];
    int l = -1, h = 300000000000005;
    while(h-l>1){
        dp[0]=mp(0,0);
        int lambda = (l+h)/2;
        ii best = mp(0,0);
        REP(i,1,N+1) {
            dp[i]=max(dp[i-1],mp(A[i]+best.fi-lambda,best.se-1));
            stMx(best,mp(dp[i].fi-A[i],dp[i].se));
        }
        if(dp[N].se>=-1*K) h=lambda;
        else l=lambda;
    }
    ii best = mp(0,0);
    REP(i,1,N+1) {
        dp[i]=max(dp[i-1],mp(A[i]+best.fi-h,best.se-1));
        stMx(best,mp(dp[i].fi-A[i],dp[i].se));
    }
    cout << dp[N].fi+h*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