Submission #1209942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209942		reginox	Feast (NOI19_feast)	C++20	100 / 100	109 ms	12176 KiB

feast

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 3e5+3;
int n, k; ll a[N];
pair<ll, int> dp[N][2];

pair<ll, int> calc(ll lam){
    dp[1][1] = make_pair(a[1] - lam, 1);
    for(int i = 2; i <= n; i++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        dp[i][1] = max(make_pair(dp[i-1][0].first + a[i] - lam, dp[i-1][0].second + 1), 
                        make_pair(dp[i-1][1].first + a[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);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int mxc = 0;
    for(int i = 1; i <= n; i++)
        if(a[i] >= 0) mxc++;
    k = min(k, mxc);
    ll L = 1, R = 1e18+1;
    while(L <= R){
        ll mid = (L+R)/2;
        if(calc(mid).second >= k) L = mid + 1;
        else R = mid - 1;
    }
    L--;
    // cout << L << " ";
    cout << calc(L).first + k * L;
    return 0;
}

• 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