Submission #370585

#	Time	Username	Problem	Language	Result	Execution time	Memory
370585		79brue	Split the sequence (APIO14_sequence)	C++14	100 / 100	617 ms	84444 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Line{
    ll a, b; int idx;
    Line(){}
    Line(ll a, ll b, int idx): a(a), b(b), idx(idx){}

    ll get(ll x){
        return a*x+b;
    }
};

double cross(Line &f, Line &g){
    if(f.a == g.a) exit(1);
    return double(g.b - f.b) / double(f.a - g.a);
}

int n, k;
ll sumSquare;
ll arr[100002], sum[100002];
ll DP[2][100002];
int idx[202][100002];
vector<Line> stk;
int pnt = 0;

void track(int x, int y){
    if(!x) return;
    track(idx[y][x], y-1);
    if(y!=k) printf("%d ", x);
}

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%lld", &arr[i]);
        sum[i] = arr[i] + sum[i-1];
    }
    sumSquare = accumulate(arr+1, arr+n+1, 0LL);
    sumSquare = sumSquare * sumSquare;

    for(int i=1; i<=n; i++) DP[0][i] = sum[i] * sum[i];
    for(int i=1; i<=k; i++){
        stk.clear();
        stk.push_back(Line(1, 2e18, -1));
        pnt = 0;
        for(int j=i; j<=n; j++){
            while(pnt < (int)stk.size()-1 && stk[pnt+1].get(sum[j]) < stk[pnt].get(sum[j])) pnt++;
            DP[i&1][j] = stk[pnt].get(sum[j]) + sum[j] * sum[j];
            idx[i][j] = stk[pnt].idx;

            Line tmp = Line(-sum[j] * 2, sum[j] * sum[j] + DP[!(i&1)][j], j);
            int ts = (int)stk.size();
            while(ts > 1 && cross(stk[ts-1], stk[ts-2]) >= cross(stk[ts-2], tmp)){
                stk.pop_back();
                ts--;
                if(pnt == ts) pnt--;
            }
            stk.push_back(tmp);
        }
    }

    printf("%lld\n", (sumSquare - DP[k&1][n]) / 2);
    track(n, k);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |         scanf("%lld", &arr[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