Submission #1287264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287264		Faisal_Saqib	Feast (NOI19_feast)	C++20	22 / 100	38 ms	22856 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,k;
const ll inf=1e18;
const int N=3e5+10;
int a[N];
ll dp[N],pre[N],sz[N];
multiset<ll> bp[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],pre[i]=a[i]+pre[i-1];
    ll bst=0,j=0;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=dp[i-1];
        sz[i]=sz[i-1];
        if(sz[i]<=k)
        {
            ans=max(ans,dp[i]);
        }
        if(sz[i]==k)
        {
            sz[i]--;
            int cnp=0;
            for(auto x:bp[j])
            {
                bp[i].insert(x);
                cnp++;
                if(cnp==4)
                {
                    break;
                }
            }
            dp[i]-=(*begin(bp[i])); // remove minimum sum used
        }
        ll c=dp[i]-pre[i];
        // if(c>=bst)
        // {
        //     bst=c;
        //     j=i;
        // }
        if(bst+pre[i]>=dp[i-1])
        {
            dp[i]=bst+pre[i];
            sz[i]=sz[j]+1;
            if(sz[i]<=k)
            {
                ans=max(ans,dp[i]);
            }
            if(sz[i]==k)
            {
                bp[i].insert(pre[i]-pre[j]);
                int cnp=0;
                for(auto x:bp[j])
                {
                    bp[i].insert(x);
                    cnp++;
                    if(cnp==4)
                    {
                        break;
                    }
                }
                dp[i]-=*begin(bp[i]);
                bp[i].erase(begin(bp[i]));
                sz[i]--;
            }
            c=max(c,dp[i]-pre[i]);
        }
        if(c>=bst)
        {
            bst=c;
            j=i;
        }
    }
    // we making new segment at i then take segment with the maximum sum else no benefit
    //  mxi  i'  i
    // say max at i'
    cout<<ans<<endl;
}

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