Submission #23474

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

sequence

/* Bismillahir Rahmanir Rahim */
 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 100005;
const int K = 205;
 
long long M[N], B[N], I[N];
int idx, ptr;
 
bool bad(int a, int b, int c){
    return (B[a] - B[b]) * (M[c] - M[a]) >= (B[a] - B[c]) * (M[b] - M[a]);
}
 
void add(long long m, long long b, int i){
    ++idx;
    M[idx] = m;
    B[idx] = b;
    I[idx] = i;
    while(idx >= 3 && bad(idx-2, idx-1, idx)){
        M[idx-1] = M[idx];
        B[idx-1] = B[idx];
        I[idx-1] = I[idx];
        idx--;
    }
}
 
inline long long query(long long x){
    if(ptr > idx) ptr = idx;
    while(ptr + 1 <= idx && M[ptr+1] * x + B[ptr+1] > M[ptr] * x + B[ptr]){
        ++ptr;
    }
    return M[ptr] * x + B[ptr];
}
 
long long A[N], sum[N], cur[N], past[N];
int nxt[N][K];
int n, k;
int marked[N];
 
int main(){
    scanf("%d %d", &n, &k);
    for(int i=1;i<=n;i++){
        scanf("%lld", &A[i]);
        sum[i] = sum[i-1] + A[i];
    }
    for(int j=1;j<=k;j++){
        idx = 0, ptr = 1;
        add(sum[1], -(sum[1] * sum[1]), 1);
        for(int i=j;i<=n;i++){
            cur[i] = query(sum[i]);
            nxt[i][j] = I[ptr];
            add(sum[i], -(sum[i] * sum[i]) + past[i], i);
            past[i] = cur[i];
        }
    }
    cout << cur[n] << endl;
    int cr = n, lf = k;
    while(lf){
        cr = nxt[cr][lf];
        marked[cr] = 1;
        lf -= 1;
    }
    int left = k;
    for(int i=1;i<=n;i++) left -= marked[i];
    for(int i=1;i<=n;i++){
        if(!marked[i] && left) marked[i] = 1, left--;
        if(marked[i]) printf("%d ", i);
    }
    cout << endl;
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:44: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:46: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