Submission #1285716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285716		c32ardash	Feast (NOI19_feast)	C++17	100 / 100	233 ms	12152 KiB

feast

#include <iostream>
#define int long long

using namespace std;

const int NMAX=3e5+5;
int n, k, v[NMAX];
struct dyn{int val, cnt;}dp[2][NMAX], ans;

dyn maxx(dyn a, dyn b)
{
    if(a.val==b.val)
        return ((a.cnt>b.cnt)?a:b);
    return ((a.val>b.val)?a:b);
}

void solve(int lambda)
{
    dp[0][0]={0, 0};
    dp[1][0]={-lambda, 1};
    for(int i=1;i<=n;i++)
    {
        dp[0][i]=maxx(dp[0][i-1], dp[1][i-1]);
        dp[1][i]=maxx({dp[0][i-1].val+v[i]-lambda, dp[0][i-1].cnt+1}, {dp[1][i-1].val+v[i], dp[1][i-1].cnt});
    }
    ans=maxx(dp[0][n], dp[1][n]);
}

int caut_bin()
{
    int r=0, pas=(1LL<<62);
    while(pas)
    {
        solve(r+pas);
        if(ans.cnt>=k)
            r+=pas;
        pas/=2;
    }
    solve(r);
    return ans.val+r*k;
}

signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    cout<<caut_bin();
    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