Submission #521588

#	Time	Username	Problem	Language	Result	Execution time	Memory
521588		pokmui9909	Feast (NOI19_feast)	C++17	100 / 100	159 ms	15064 KiB

feast

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second
ll N, K;
ll A[300005];
pair<ll, ll> D[300005][2];
pair<ll, ll> f(ll lmb){
    for(int i = 1; i <= N; i++){
        D[i][0] = max(D[i - 1][0], make_pair(D[i - 1][1].x - lmb, D[i - 1][1].y - 1));
        D[i][1] = max(D[i - 1][0], D[i - 1][1]);
        D[i][1].x += A[i];
    }
    return max(D[N][0], make_pair(D[N][1].x - lmb, D[N][1].y - 1));
}
 
int main(){
    cin.tie(0) -> sync_with_stdio(false);
    
    cin >> N >> K;
    for(int i = 1; i <= N; i++){
        cin >> A[i];
    }
    ll L = 0, R = 3e14 + 7;
    while(L <= R){
        ll m = (L + R) / 2;
        if(-f(m).y <= K) R = m - 1;
        else L = m + 1;
    }
    cout << f(L).x + L * 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