Submission #365057

#	Time	Username	Problem	Language	Result	Execution time	Memory
365057		qwerasdfzxcl	Split the sequence (APIO14_sequence)	C++14	100 / 100	1004 ms	84220 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int a[100100];
ll s[100100], dp[100100], tmp[100100];
vector<int> fx;
long double ran[100100];
int n, k;
int parent[100100][202];

pair<long double, bool> po(int x1, int x2){
    if (s[x1]==s[x2]) return make_pair(0, 0);
    pair<long double, bool> ret=make_pair(0, 1);
    ll tmp1=s[x2]*s[x2]-s[x1]*s[x1]+tmp[x2]-tmp[x1];
    ll tmp2=s[x2]*2-s[x1]*2;
    ret.first=(long double)tmp1/tmp2;
    return ret;
}

void cht(int t){
    int cur=0;
    dp[0]=1e18;
    for (int i=1;i<n;i++){
        if (i<t){
            dp[i]=1e18;
            continue;
        }
        if (i==t){
            fx.push_back(i-1);
            dp[i]=s[i-1]*(-2)*s[i]+tmp[i-1]+(s[i-1]*s[i-1])+(s[i]*s[i]);
            parent[i][t]=i-1;
            continue;
        }
        pair<long double, bool> tmpp=po(fx.back(), i-1);
        while(tmpp.second && tmpp.first<ran[(int)fx.size()-1]){
            ran[(int)fx.size()-1]=1e20;
            fx.pop_back();
            tmpp=po(fx.back(), i-1);
        }
        if (tmpp.second){
            ran[(int)fx.size()]=tmpp.first;
            fx.push_back(i-1);
        }
        if (cur>=((int)fx.size()-1)){
            cur=(int)fx.size()-1;
        }
        for (;cur<(int)fx.size()-1;cur++){
            if ((long double)s[i]>ran[cur+1]) continue;
            break;
        }
        for (;cur>0;cur--){
            if ((long double)s[i]<ran[cur]) continue;
            break;
        }
        assert(ran[cur]<=(long double)s[i] && (long double)s[i]<=ran[cur+1]);
        //printf("%d %d\n", t, i);
        //for (int j=0;j<=(int)fx.size();j++) printf("%Lf ", ran[j]);
        //printf("\n");
        dp[i]=s[fx[cur]]*(-2)*s[i]+tmp[fx[cur]]+(s[fx[cur]]*s[fx[cur]])+(s[i]*s[i]);
        parent[i][t]=fx[cur];
    }
    for (int i=0;i<n;i++){
        //printf("%lld ", dp[i]);
        tmp[i]=dp[i];
    }
    //printf("\n");
}

int main(){
    scanf("%d %d", &n, &k);
    for (int i=0;i<n;i++) scanf("%d", a+i);
    s[0]=a[0];
    for (int i=1;i<n;i++) s[i]=s[i-1]+a[i];
    for (int i=0;i<n;i++){
        tmp[i]=s[i]*s[i];
    }
    for (int i=0;i<n;i++) parent[i][0]=-1;
    for (int i=1;i<=k;i++){
        fx.clear();
        ran[0]=-1e20;
        fill(ran+1, ran+n+3, 1e20);
        cht(i);
    }
    printf("%lld\n", (s[n-1]*s[n-1]-dp[n-1])/2);
    //printf("%d\n", parent[n-1][k]);
    int idx=k-1;
    for (int i=parent[n-1][k];i!=-1;i=parent[i][idx--]){
        printf("%d ", i+1);
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:72:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |     for (int i=0;i<n;i++) 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: 29 / 29