Submission #558558

#	Time	Username	Problem	Language	Result	Execution time	Memory
558558		stefantaga	Feast (NOI19_feast)	C++14	100 / 100	341 ms	12772 KiB

feast

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n,i,k;
ll v[300005],din[300005],cnt[300005],sum[300005];
ll suma(int st,int dr)
{
    return sum[dr]-sum[st-1];
}
ll ok (ll mij)
{
    deque <int> st;
    st.push_back(0);
    for (int i=1; i<=n; i++)
    {
        din[i]=din[i-1];
        cnt[i]=cnt[i-1];
        if (din[i]<din[i-1]+mij)
        {
            din[i]=din[i-1]+mij;
            cnt[i]=cnt[i-1]+1;
        }
        if (st.empty())
        {
            if (din[i]<v[i]+din[i-1]+mij)
            {
                din[i]=v[i]+din[i-1]+mij;
                cnt[i]=1+cnt[i-1];
            }
        }
        else
        {
            if (din[i]<din[st.front()]+suma(st.front()+1,i)+mij)
            {
                din[i]=din[st.front()]+suma(st.front()+1,i)+mij;
                cnt[i]=1+cnt[st.front()];
            }
        }
        while (!st.empty()&&din[st.back()]+suma(st.back()+1,i+1)<=v[i+1]+din[i])
        {
            st.pop_back();
        }
        st.push_back(i);
    }
    return cnt[n];
}
ll st,dr,sol;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
#ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
#endif // HOME
    cin>>n>>k;
    for (i=1; i<=n; i++)
    {
        cin>>v[i];
        sum[i]=sum[i-1]+v[i];
    }
    st=-1e16;
    dr=1e16;
    while (st<=dr)
    {
        ll mij = (st+dr)/2;
        auto salut = ok(mij);
        if (salut>=k)
        {
            sol=mij;
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    deque <int> st;
    st.push_back(0);
    for (int i=1; i<=n; i++)
    {
        din[i]=din[i-1];
        cnt[i]=cnt[i-1];
        if (din[i]<din[i-1]+sol)
        {
            din[i]=din[i-1]+sol;
            cnt[i]=cnt[i-1]+1;
        }
        if (st.empty())
        {
            if (din[i]<v[i]+din[i-1]+sol)
            {
                din[i]=v[i]+din[i-1]+sol;
                cnt[i]=1+cnt[i-1];
            }
        }
        else
        {
            int poz=st.front();
            if (din[i]<din[poz]+suma(poz+1,i)+sol)
            {
                din[i]=din[poz]+suma(poz+1,i)+sol;
                cnt[i]=1+cnt[poz];
            }
        }
        while (!st.empty()&&din[st.back()]+suma(st.back()+1,i+1)<=v[i+1]+din[i])
        {
            st.pop_back();
        }
        st.push_back(i);
    }
    cout<<din[n]-cnt[n]*sol;
    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