Submission #209995

#	Time	Username	Problem	Language	Result	Execution time	Memory
209995		my99n	Split the sequence (APIO14_sequence)	C++14	71 / 100	1390 ms	131076 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100100], s[100100], dp[2][100100];
vector<int> mxk[2][100100];

// dp[i][j] = maximizing dp[i^1][k] + (s[j]-s[k]) * (s[k])
//          = maxing dp[i^1][k] + s[j]s[k] - s[k]s[k] in the form mj+c

struct line { ll m, c, k; };
bool bad (line &a, line &b, line c) { return (a.c-c.c)*(b.m-a.m) <= (a.c-b.c)*(c.m-a.m); }
line l[1000100];
int front = 0, back = 0;
void add (ll m, ll c, ll k) {
    while (back > 2 and bad(l[back-2], l[back-1], {m, c})) back--;
    l[back++] = {m, c, k};
}
pair<ll,ll> query (ll x) {
    if (front >= back) front = back-1;
    while (front < back-1 and l[front].m*x+l[front].c <= l[front+1].m*x+l[front+1].c) front++;
    return {l[front].m * x + l[front].c, l[front].k};
}

int main(){
    int n, k; scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), s[i] = s[i-1]+a[i];
    for (int i = 1; i <= k; i++) {
        front = back = 0;
        memset(l, 0, sizeof l);
        dp[i%2][1] = 0;
        add(s[1], dp[(i+1)%2][1] - s[1]*s[1], 1);
        for (int j = 2; j <= n; j++) {
            dp[i%2][j] = query(s[j]).first;
            int k = query(s[j]).second;
            mxk[i%2][j].clear();
            mxk[i%2][j].push_back(k);
            for (auto x : mxk[(i+1)%2][k]) mxk[i%2][j].push_back(x);
            add(s[j], dp[(i+1)%2][j] - s[j]*s[j], j); 
        }
    }
    printf("%lld\n", dp[k%2][n]);
    for (auto x : mxk[k%2][n]) printf("%d ", x);
    return 0;
}
// 7 3 4 1 3 4 0 2 3

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:25:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n, k; scanf("%d %d", &n, &k);
               ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:26:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), s[i] = s[i-1]+a[i];
                                  ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

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