Submission #1209985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209985		44100	Feast (NOI19_feast)	C++20	100 / 100	107 ms	12176 KiB

feast

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pub push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll Max=3e5+5;
pll dp[Max][2];
ll a[Max],n,k;
pll process(ll la)
{
    ll i,j;
    dp[1][0]={0,0};
    dp[1][1]={a[1]-la,1};
    for(i=2;i<=n;++i)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=max(mp(dp[i-1][0].fi+a[i]-la,dp[i-1][0].se+1),mp(dp[i-1][1].fi+a[i],dp[i-1][1].se));
    }
    pll res=max(dp[n][0],dp[n][1]);
    return res;
}
ll solve()
{
    ll i,j,l,r;
    l=0;
    r=1e18;
    while(l<r)
    {
        ll mid=(l+r+1)>>1;
        pll res=process(mid);
        if(res.se>=k)
            l=mid;
        else r=mid-1;
    }
    pll fi_res=process(l);
    return fi_res.fi+l*k;
}
ll solve2()
{
    ll i,j,l,r;
    l=0;
    r=1e18;
    //cout<<l<<" "<<r<<"\n";
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        pll res=process(mid);
        //cout<<"mid="<<mid<<" dp="<<res.fi<<" cnt="<<res.se<<"\n";
        if(res.se==k)
        {
            /*for(i=1;i<=n;++i)
            {
                cout<<i<<".\n";
                auto x=dp[i][0];
                cout<<"dp="<<x.fi<<" cnt="<<x.se<<"\n";
                x=dp[i][1];
                cout<<"dp="<<x.fi<<" cnt="<<x.se<<"\n";
            }*/
            return res.fi+res.se*mid;
        }
        if(res.se>k)
            l=mid+1;
        else r=mid-1;
    }
    return 0;
}
int main()
{
    fast
    ll i,j;
    cin>>n>>k;
    for(i=1;i<=n;++i)
        cin>>a[i];
    ll ans=solve();
    cout<<ans<<"\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