Submission #242824

#	Time	Username	Problem	Language	Result	Execution time	Memory
242824		gs18115	Feast (NOI19_feast)	C++14	71 / 100	1041 ms	162996 KiB

feast

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
inline void clear(vector<ll>&v)
{
    v.clear();
    v.shrink_to_fit();
    return;
}
inline void merge(vector<ll>&rt,vector<ll>&l,vector<ll>&r)
{
    rt.clear();
    rt.reserve((int)l.size()+(int)r.size()-1);
    rt.eb(l[0]+r[0]);
    int li=1,ri=1;
    while(li<(int)l.size()&&ri<(int)r.size())
    {
        if(l[li]-l[li-1]>r[ri]-r[ri-1])
            rt.eb(rt.back()+l[li]-l[li-1]),li++;
        else
            rt.eb(rt.back()+r[ri]-r[ri-1]),ri++;
    }
    while(li<(int)l.size())
        rt.eb(rt.back()+l[li]-l[li-1]),li++;
    while(ri<(int)r.size())
        rt.eb(rt.back()+r[ri]-r[ri-1]),ri++;
    return;
}
inline void mx(vector<ll>&rt,vector<ll>&r)
{
    if(rt.size()<r.size())
        rt.resize(r.size(),-INF);
    for(int i=0;i<(int)r.size();i++)
        rt[i]=max(rt[i],r[i]);
    return;
}
vector<ll>no[1200010],l[1200010],r[1200010],lr[1200010];
void dnc(int n,int s,int e,vector<ll>&v)
{
    if(s==e)
    {
        no[n].eb(0);
        no[n].eb(v[s]);
        l[n].eb(v[s]);
        r[n].eb(v[s]);
        lr[n].eb(v[s]);
        return;
    }
    int m=s+(e-s)/2;
    dnc(n*2,s,m,v);
    dnc(n*2+1,m+1,e,v);
    vector<ll>v1,v2,v3,v4;
    merge(no[n],no[n*2],no[n*2+1]);
    merge(l[n],lr[n*2],l[n*2+1]);
    merge(r[n],r[n*2],lr[n*2+1]);
    merge(lr[n],lr[n*2],lr[n*2+1]);
    merge(v1,r[n*2],l[n*2+1]);
    merge(v2,l[n*2],no[n*2+1]);
    merge(v3,no[n*2],r[n*2+1]);
    merge(v4,l[n*2],r[n*2+1]);
    v1.insert(v1.begin(),-INF);
    v4.insert(v4.begin(),-INF);
    mx(no[n],v1);
    mx(l[n],v2);
    mx(r[n],v3);
    mx(lr[n],v4);
    for(int i=n*2;i<n*2+2;i++)
        clear(no[i]),clear(l[i]),clear(r[i]),clear(lr[i]);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<ll>v(n);
    for(ll&t:v)
        cin>>t;
    if(k==1)
    {
        ll ans=0;
        ll ca=0;
        for(ll&t:v)
            ans=max(ans,ca=max(ca+t,0ll));
        cout<<ans<<endl;
        return 0;
    }
    bool allp=1;
    for(ll&t:v)
        if(t<0)
            allp=0;
    if(allp)
    {
        ll ans=0;
        for(ll&t:v)
            ans+=t;
        cout<<ans<<endl;
        return 0;
    }
    v.insert(v.begin(),0ll);
    dnc(1,1,n,v);
    ll ans=0;
    for(int i=0;i<=k;i++)
        ans=max(ans,no[1][i]);
    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: 0 / 29