Submission #1017643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017643		vjudge1	Feast (NOI19_feast)	C++17	0 / 100	196 ms	2660 KiB

feast

#include <bits/stdc++.h>
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const int mxN = 3e5 + 5;
const int mod = 1e9 + 7;
using namespace std;
bool operator>(pair<ll,int> a,pair<ll,int>b){
    return make_pair(a.F,-1 * a.S) > make_pair(b.F, -1 * b.S);
}
bool operator<(pair<ll,int> a,pair<ll,int>b){
    return make_pair(a.F,-1 * a.S) < make_pair(b.F, -1 * b.S);
}
int n,k;
ll a[mxN];
pair<ll,int> dp[2][2];
pair<ll,int> num;
ll ans;
bool solve(int lam){
    // cout<<lam<<'\n';
    for(int i = 0;i <= 1;i++){
        dp[i][0] = make_pair(0,0);
        dp[i][1] = make_pair(0,0);
    }
    for(int i = 1;i <= n;i++){
        // cout<<(i & 1)<<' '<<(~i & 1)<<'\n';
        dp[(i & 1)][0] = max(dp[(~i & 1)][0],dp[(~i & 1)][1]);
        dp[(i & 1)][1] = make_pair(dp[(~i & 1)][0].F + a[i] - lam,dp[~i & 1][0].S + 1);
        if(i > 1) dp[(i & 1)][1] = max(dp[(i & 1)][1],make_pair(dp[~i & 1][1].F + a[i],dp[~i & 1][1].S));
        // cout<<dp[(i & 1)][0].F<<' '<<dp[(i & 1)][0].S<<' '<<dp[(i & 1)][1].F<<' '<<dp[(i & 1)][1].S<<'\n';
    }
    num = max(dp[n & 1][0],dp[n & 1][1]);
    // cout<<num.F<<' '<<num.S<<'\n';
    return (num.S <= k);
}
signed main(){
    // cout<<"TEST";
    cin >>n>>k;
    for(int i = 1;i <= n;i++) cin >>a[i];
    ll l = 0,r = 1e16,md;
    int binit = 60;
    while(l < r){
        md = (l + r) / 2;
        if(solve(md)){
            r = md;
            ans = num.F + num.S * md;
        }else l = md + 1;
    }
    cout<<ans;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:42:9: warning: unused variable 'binit' [-Wunused-variable]
   42 |     int binit = 60;
      |         ^~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29