Submission #33923

#	Time	Username	Problem	Language	Result	Execution time	Memory
33923		petil	Split the sequence (APIO14_sequence)	C++14	71 / 100	2000 ms	92180 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct CHT{
    struct line{
        ll s, t;
        int idx;
    };
    deque<line> que;
    bool ck(line L1, line L2, line me){
        ///x1 =   (L1.t-L2.t) /(L2.s-L1.s)
        ///x2 =   (L2.t - me.t) / (me.s-L2.s)
        ///x1<x2
        return (L1.t-L2.t) * (me.s-L2.s) < (L2.t-me.t) * (L2.s-L1.s) ;
    }

    void push(line me){

        while((int)que.size()>=2 && !ck(que[(int)que.size()-2], que.back(), me)){
            que.pop_back();
        }
        if(!que.empty() && que.back().s == me.s){
            if(que.back().t>=me.t)return;
            que.pop_back();que.push_back(me);
        }
        else{
            que.push_back(me);
        }
    }
    ll val(line li, ll x)
    {
        return li.s * x + li.t;
    }
    void Efront(ll x)
    {
        while((int)que.size()>=2 && !(val(que[0], x)>val(que[1], x))){
          //  if(que[1].idx == id)return;
            que.pop_front();
        }
    }
    ll maxval(ll x, ll tt){
        return tt + val(que[0], x);
    }

};

int n, k, A[100005];
ll rs[100005], dp[100005];
int pre[100003][202];
void trace(int now, int j)
{
    vector<int> tmp;
    while(1){
        if(j==0)break;
        tmp.push_back(now);
        now = pre[now][j];--j;
    }
    for(int i=(int)tmp.size()-1; i>=0; i--)
        cout<<tmp[i]<<" ";
}

int main()
{
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%d", &A[i]);
    }
    for(int i=n; i>=1; i--){
        rs[i] = rs[i+1]+(ll)A[i];
    }

    vector<pair<pair<ll ,ll>, int> > tmp;
    vector<pair<pair<ll ,ll>, int> > tmp2;

    tmp.push_back({{-rs[1], 0}, 0});

    for(int j=1; j<=k; j++){
        CHT cht;
        int pos = 0;
        for(int i=j; i<=n; i++){\
            if(j&1){
            while(pos<(int)tmp.size() && tmp[pos].second<i){
                cht.push({tmp[pos].first.first, tmp[pos].first.second, tmp[pos].second});
                ++pos;
            }
            }
            else{
                while(pos<(int)tmp2.size() && tmp2[pos].second<i){
                cht.push({tmp2[pos].first.first, tmp2[pos].first.second, tmp2[pos].second});
                ++pos;
            }
            }

            cht.Efront(-rs[i+1]);
            dp[i] = cht.maxval(-rs[i+1], -(ll)rs[i+1]*rs[i+1]);
            ///nxt.push({-rs[i+1], dp[i], i});
            if(j&1)
            tmp2.push_back({{-rs[i+1], dp[i]}, i});
            else
                tmp.push_back({{-rs[i+1], dp[i]}, i});
            pre[i][j] = cht.que[0].idx;
        }
        if(j&1)
            tmp.clear();
        else
            tmp2.clear();

    }
    ll ans=-1, ed=-1;
    for(int i=k; i<=n; i++){
        if(ans<dp[i]){
            ans = dp[i];ed=i;
        }
    }

    cout<<ans<<endl;

    trace(ed, k);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:64:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
                           ^
sequence.cpp:66:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
                           ^

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29