Submission #1209938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209938		reginox	Feast (NOI19_feast)	C++20	18 / 100	99 ms	12104 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[0][1] = {-1e18, 0};
    for(int i = 1; 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 = 0, R = 1e18+1;
    while(L <= R){
        ll mid = (L+R)/2;
        if(calc(mid).second >= k) L = mid + 1;
        else R = mid - 1;
    }
    // cout << L << " ";
    L--;
    cout << calc(L).first + k * L;
    return 0;
}

• 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