Submission #209982

#	Time	Username	Problem	Language	Result	Execution time	Memory
209982		my99n	Split the sequence (APIO14_sequence)	C++14	0 / 100	56 ms	14456 KiB

sequence

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

long long 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]-s[0])
//          = maxing dp[i^1][k] + s[j](s[k]-s[0]) - s[k](s[k]-s[0]) in the form mj+c
struct line { long long m, c, k; };
deque<line> l;
bool bad (line a, line b, line c) { return (a.c-b.c)*(c.m-a.m) >= (a.c-c.c)*(b.m-a.m); }
void add (int m, int c, int k) {
    while (l.size() > 1 and bad(l[l.size()-1], l[l.size()], {m, c})) l.pop_back();
    l.push_back({m, c, k});
}
pair<long long, long long> query (int x) {
    while (l[0].m*x+l[0].c <= l[1].m*x+l[1].c) l.pop_front();
    return {l[0].m*x+l[0].c, l[0].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++) {
        while (!l.empty()) l.pop_back();
        dp[i%2][1] = 0;
        add(s[1]-s[0], dp[(i+1)%2][1] - s[1]*(s[1]-s[0]), 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]-s[0], dp[(i+1)%2][j] - s[j]*(s[j]-s[0]), 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:22: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:23: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: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29