Submission #209976

#	Time	Username	Problem	Language	Result	Execution time	Memory
209976		my99n	Split the sequence (APIO14_sequence)	C++14	22 / 100	2105 ms	112248 KiB

sequence

#include<bits/stdc++.h>
using namespace std;

long long a[100100], s[100100], dp[2][100100];
vector<int> mxk[2][100100];

void solve (int i, int n) {
    int k = 1, j = 1;
    while (j <= n) {
        long long nw = dp[i^1][k] + (s[j]-s[k])*(s[k]-s[0]);
        long long nx = dp[i^1][k+1] + (s[j]-s[k+1])*(s[k+1]-s[0]);
        if (k == j-1) nx = 0;
        if (nx >= nw) {
            k++; continue;
        }
        dp[i][j] = nw;
        mxk[i][j].clear();
        mxk[i][j].push_back(k);
        for (auto x : mxk[i^1][k]) mxk[i][j].push_back(x);
        j++;
    }
}

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++) solve(i%2, n);
    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: 0 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29