Submission #575339

#	Time	Username	Problem	Language	Result	Execution time	Memory
575339		handlename	Split the sequence (APIO14_sequence)	C++17	100 / 100	1092 ms	93812 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
deque<pair<long long,long long> > dq[201];
deque<int> id[201];
long long f(pair<long long,long long> line, long long x){
    return line.first*x + line.second;
}
pair<long long,int> qry(long long x,int num){
    while(dq[num].size()>1){
        if(f(dq[num][0],x)<f(dq[num][1],x)){
            dq[num].pop_front();
            id[num].pop_front();
        }
        else break; 
    }
    return make_pair(f(dq[num][0],x),id[num][0]);
}
long double intersect(long long m1, long long c1, long long m2, long long c2){
    return (long double)(c2-c1)/(m1-m2);
}
long double intersect(pair<long long,long long> p1, pair<long long,long long> p2){
    return intersect(p1.first,p1.second,p2.first,p2.second);
}
void ins(long long m,long long c,int index,int num) {//insert line y=mx+c
    pair<long long,long long> line=make_pair(m,c);
    while (dq[num].size()>1) {
        long long s=dq[num].size();
        if (intersect(dq[num][s-1],line)<=intersect(dq[num][s-2],line)){
            dq[num].pop_back();
            id[num].pop_back();
        }
        else break;
    }
    dq[num].push_back(line);
    id[num].push_back(index);
}
long long n,k;
long long arr[100001],pre[100001];
int dp[100001][201];
bool vis[100001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k;
    for (int i=1;i<=n;i++) cin>>arr[i];
    for (int i=1;i<=n;i++) pre[i]=pre[i-1]+arr[i];
    for (int i=0;i<=k;i++){
        ins(0,0,0,i);
    }
    long long ans=-1,pos=1;
    for (int i=1;i<n;i++){
        for (int j=k;j>=1;j--){
            pair<long long,int> cur=qry(pre[i]-pre[n],j-1);
            cur.first+=pre[i]*(pre[n]-pre[i]);
            //dp[x][j-1].first+(pre[i]-pre[x])*(pre[n]-pre[i]);
            ins(pre[i],cur.first,i,j);
            dp[i][j]=cur.second;
            assert(i!=cur.second);
            if (j==k){
                if (cur.first>=ans){
                    ans=cur.first;
                    pos=i;
                }
            }
        }
    }
    cout<<ans<<'\n';
    while (pos!=0 && k>0){
        cout<<pos<<' ';
        vis[pos]=true;
        pos=dp[pos][k];
        k--;
    }
    for (int i=1;i<n;i++){
        if (k==0) break;
        if (!vis[i]){
            cout<<i<<' ';
            k--;
        }
    }
}

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