Submission #1209995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209995		shiozzz	Feast (NOI19_feast)	C++20	100 / 100	104 ms	12168 KiB

feast

// -sudo hikaru 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vl;
typedef vector<pair<long long, long long>> vpl;
#define For(i,a,b) for(ll i=a;i<b;i++)

const ll MAXN = 3*1e5+7;
const ll MOD = 1e9+7;
ll n, k, a[MAXN];

auto solve(ll lmb){
    pair<ll, ll> dp[n][2];
    dp[0][0] = {0,0};
    dp[0][1] = {a[0]-lmb, 1};

    For(i,1,n){
        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] - lmb, dp[i - 1][0].second + 1), make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
    }
    return max(dp[n-1][0], dp[n-1][1]);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    For(i,0,n) cin >> a[i];
    ll l = 0, r = 1e18;
    while(l<r){
        ll m = (l+r+1)/2;
        solve(m).second >= k ? l = m : r = m-1;
    }
    cout << solve(l).first + l*k << "\n";
    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