Submission #994480

#	Time	Username	Problem	Language	Result	Execution time	Memory
994480		idiotcomputer	Feast (NOI19_feast)	C++11	100 / 100	105 ms	4676 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pii pair<ll,ll>
#define f first
#define s second

const int mxN = 3e5;
int n,k;
int a[mxN];

pii test(ll v){
    pii dp[2];
    pii dp2[2];
    dp[0] = {0,0};
    dp[1] = {0,0};
    for (int i = 0; i < n; i++){
        dp2[0] = max(dp[0],(pii){dp[1].f-v,dp[1].s+1});
        dp2[1] = max((pii) {dp[0].f+a[i],dp[0].s}, (pii) {dp[1].f+a[i],dp[1].s});
        swap(dp2,dp);
    }
    dp[1] = (pii) {dp[1].f-v,dp[1].s+1};
    return max(dp[0],dp[1]);
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    ll l = 0;
    ll r = 1e15;
    ll c;
    while (r-l>1){
        c = (l+r)/2;
        if(test(c).s<k) r = c;
        else l = c;
    }
    pii t = test(l);
   // cout << l << " -=  " << t.f << " " << t.s << '\n';
    cout << t.f + k*l << "\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