Submission #34098

#	Time	Username	Problem	Language	Result	Execution time	Memory
34098		wan2000	Split the sequence (APIO14_sequence)	C++14	100 / 100	609 ms	88468 KiB

sequence

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

template<typename T> inline void read(T &x){
    x = 0; char ch; while(!isdigit(ch=getchar()));
    do{ x = 10*x+ch-'0'; } while(isdigit(ch=getchar()));
}

typedef long long ll;
typedef pair<ll,ll> pll;

const int N = 100001;
const int K = 201;

int n, k, Tr[K][N], pnt, s;
ll A[N], S[N], F[2][N], res;
vector<pair<pll,int> > L, D;

bool maxi(ll &x, ll y){
    if(x<y) x = y;
    else return 0;
    return 1;
}

void BackTrack(int x, int d){
    if(d==0) return;
    cout<<x<<' ';
    BackTrack(Tr[d][x],d-1);
}

bool bad(pll a, pll b, pll c){
    return (c.Y-a.Y)*(a.X-b.X)>=(b.Y-a.Y)*(a.X-c.X);
}

void add(pair<pll,int> p){
    while(L.size()>=2&&bad(L[L.size()-2].X,L.back().X,p.X)){
        L.pop_back();
    }
    L.push_back(p);
}

ll get(ll x, int d, int u){
    if(pnt>=(int)L.size()) pnt = L.size()-1;
    while(pnt<(int)L.size()-1&&L[pnt+1].X.X*x+L[pnt+1].X.Y>L[pnt].X.X*x+L[pnt].X.Y){
        pnt++;
    }
    Tr[d][u] = L[pnt].Y;
    return L[pnt].X.X*x+L[pnt].X.Y;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    read(n); read(k);
    for(int i = 1; i <= n; i++){
        read(A[i]);
        S[i] = S[i-1]+A[i];
    }
    for(int ii = 1; ii <= k; ii++){
        pnt = 0;
        L.clear();
        for(int i = n-ii; i >= 1; i--){
            add(mp(mp(S[i+1],F[(ii+1)%2][i+1]),i+1));
            F[ii%2][i] = get(S[i],ii,i)-S[i]*S[i];
        }
    }
    res = -1;
    for(int i = 1; i <= n-1; i++){
        if(maxi(res,F[k%2][i])){
            s = i;
        }
    }
    cout<<res<<'\n';
    BackTrack(s,k);
    return 0;
}

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