Submission #33807

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

sequence

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

#define llint long long
#define fi first
#define se second

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];
int t[maxN][maxM];
vector<llint> A, B;
vector<int> id;
int pointer;
//y = A * x + B;

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

void clear() {
    A.resize(0);
    B.resize(0);
    id.resize(0);
    pointer = 0;
}

bool bad(int l1, int l2, int l3) {
    return (B[l3] - B[l1]) * (A[l1] - A[l2]) 
        <= (B[l2] - B[l1]) * (A[l1] - A[l3]);
}

void add(llint a, llint b, int i) {
    A.push_back(a);
    B.push_back(b);
    id.push_back(i);

    while (A.size() >= 3 && bad(A.size()-3, A.size() - 2, A.size() - 1)) {
        A.erase(A.end() - 2);
        B.erase(B.end() - 2);
        id.erase(id.end() - 2);
    }
}

pair<llint, int> query(llint x) {
    if (pointer >= A.size())
        pointer = A.size() - 1;

    while (pointer < A.size() - 1 &&
            A[pointer] * x + B[pointer] 
            < A[pointer + 1] * x + B[pointer + 1]) 
        pointer++;
    
    return {A[pointer] * x + B[pointer], id[pointer]};
}

inline void solve() {
    for (int k = 1; k <= K; ++k) {
        clear();
        add(0, 0, 0);
        for (int i = k; i <= N; ++i) {
            pair<llint, int> best = query(a[i]);
            f[i][k&1] = best.fi;
            t[i][k] = best.se;

            add(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 'std::pair<long long int, int> query(long long int)':
sequence.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pointer >= A.size())
                 ^
sequence.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pointer < A.size() - 1 &&
                    ^
sequence.cpp: In function 'void enter()':
sequence.cpp:31: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:33:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &a[i]);
                             ^

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