Submission #33784

#	Time	Username	Problem	Language	Result	Execution time	Memory
33784		ztrong	Split the sequence (APIO14_sequence)	C++14	71 / 100	2000 ms	86944 KiB

sequence

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

#define llint long long

void openFile() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
#ifdef Tr___
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
}

const int maxN = 1e5 + 5;
const int maxM = 2e2 + 5;
const llint INF = 1e9 + 7;

int N, K;
llint a[maxN];
llint f[maxN][2];
struct line {
    llint a, b;
    int id;
    line() {}
    line(llint a, llint b, int id): a(a), b(b), id(id) {}
} l[maxN];
int nLines = 0;
int last = 0;

inline void enter() {
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; ++i) {
        scanf("%lld", &a[i]);
        a[i] += a[i - 1];
    }
}

inline void clear() {
    nLines = 0;
    last = 1;
}

inline bool bad(const line &a, const line &b, const line &c) {
    return (a.b - c.b) * (-a.a + b.a) <= (c.a - a.a) * (-b.b + a.b);
}

inline void update(const line &o) {
    while (nLines >= 2 
            && bad(l[nLines - 1], l[nLines], o)) 
        --nLines;
    l[++nLines] = o;
}

inline llint get(int id, llint x) {
    return l[id].a * x + l[id].b;
}

inline int query(llint x) {
    //so important!!!
    if (last > nLines) 
        last = nLines;
    last = max(last, 1);
    if (nLines == 0) return 0;
    while (last < nLines && get(last, x) < get(last + 1, x)) ++last;
    return last;
}

int t[maxN][maxM];

inline void solve() {
    int la;
    for (int k = 1; k <= K; ++k) {
        clear();
        for (int i = k; i <= N; ++i) {
            la = query(a[i]);
            f[i][k&1] = get(la, a[i]);
            t[i][k] = l[la].id;

            update(line(a[i], f[i][!(k&1)] - a[i] * a[i], i));
        }
    }

    printf("%lld\n", f[N][K&1]);
    int trace = t[N][K];
    while (trace) {
        printf("%d ", trace);
        trace = t[trace][--K];
    }
}

int main() {
    openFile();
    enter();
    solve();
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void enter()':
sequence.cpp:32:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &K);
                           ^
sequence.cpp:34:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &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