Submission #241774

#	Time	Username	Problem	Language	Result	Execution time	Memory
241774		nicolaalexandra	Split the sequence (APIO14_sequence)	C++14	100 / 100	672 ms	84348 KiB

sequence

#include <bits/stdc++.h>
#define DIM 100001
#define DIMK 201
#define INF 2000000000
using namespace std;

struct dreapta{
    long long a,b;
} w[DIM];

int v[DIM],fth[DIM][DIMK],d[DIM];
long long dp[DIM][2],sp[DIM];
vector <int> sol;
int n,k,i,j,p,u;

/*int intersectie (dreapta c, dreapta b, dreapta a){
    return (a.b - c.b) * (a.a - b.a) < (b.b - a.b) * (c.a - a.a);
}*/
long double intersectie (dreapta a, dreapta b){
    if (a.a == b.a)
        return INF;
    return 1.0 * (a.b - b.b) / (b.a - a.a);
}

long long f (long long a, long long b, long long x){
    return a*x + b;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>k;
    for (i=1;i<=n;i++){
        cin>>v[i];
        sp[i] = sp[i-1] + v[i];
    }

    for (i=1;i<n;i++)
        dp[i][1] = sp[i] * (sp[n] - sp[i]);

    int t = 0;
    for (j=2;j<=k;j++){
        p = 1, u = 0;
        for (i=j;i<=n;i++){

            w[i-1].a = sp[i-1], w[i-1].b = dp[i-1][1-t] - sp[i-1] * sp[n];


            while (u > p && intersectie(w[d[u]],w[d[u-1]]) > intersectie(w[d[u-1]],w[i-1]))
                u--;
            d[++u] = i-1;

            while (p < u && f (w[d[p]].a,w[d[p]].b,sp[i]) <= f (w[d[p+1]].a,w[d[p+1]].b,sp[i]))
                p++;


            dp[i][t] = sp[i] * sp[n] - sp[i] * sp[i] + f (w[d[p]].a,w[d[p]].b,sp[i]);
            fth[i][j] = d[p];

        }
        t = 1-t;
    }

    int x, y = k;
    long long maxi = -1;
    for (i=1;i<=n;i++)
        if (dp[i][1-t] > maxi)
            maxi = dp[i][1-t], x = i;

    cout<<maxi<<"\n";

    sol.push_back(x);
    while (x){
        sol.push_back(fth[x][y]);
        x = fth[x][y];
        y--;
    }

    for (i=sol.size()-2;i>=0;i--)
        cout<<sol[i]<<" ";

    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