Submission #1165632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165632		12345678	Feast (NOI19_feast)	C++17	100 / 100	97 ms	2764 KiB

feast

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=3e5+5, inf=1e18;

ll n, qs[nx], l=0, r=inf, k;
pair<ll, ll> dp, mx;

void solve(ll x)
{
    mx={0, 0}, dp={0, 0};
    for (int i=1; i<=n; i++)
    {
        dp=max(dp, {mx.first+qs[i]-x, mx.second-1});
        mx=max(mx, {dp.first-qs[i], dp.second});
    }
}
int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>qs[i], qs[i]+=qs[i-1];
    while (l<r)
    {
        ll md=(l+r)/2;
        //cout<<md<<' '<<dp.first<<' '<<dp.second<<'\n';
        solve(md);
        if (-dp.second<=k) r=md;
        else l=md+1;
    }
    //cout<<"l "<<l<<'\n';
    solve(l);
    cout<<dp.first+l*k;
}

/*
find minimum lambda that make taking <= k pieces optimal
*/

• 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