Submission #23475

#	Time	Username	Problem	Language	Result	Execution time	Memory
23475		rubabredwan	Split the sequence (APIO14_sequence)	C++14	100 / 100	469 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;
  
void add(long long m, long long b, int i){
    ++idx, M[idx] = m, B[idx] = b, I[idx] = i;
    while(idx >= 3 && (B[idx-2] - B[idx-1]) * (M[idx] - M[idx-2]) >= (B[idx-2] - B[idx]) * (M[idx-1] - M[idx-2])){
        M[idx-1] = M[idx], B[idx-1] = B[idx], I[idx-1] = I[idx], idx--;
    }
}
 
long long query(long long x){
}
 
long long A[N], sum[N], cur[N], past[N];
int nxt[K][N];
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++){
            if(ptr > idx) ptr = idx;
            while(ptr + 1 <= idx && M[ptr+1] * sum[i] + B[ptr+1] > M[ptr] * sum[i] + B[ptr]) ++ptr;
            cur[i] = M[ptr] * sum[i] + B[ptr];
            nxt[j][i] = 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[lf][cr];
        marked[cr] = 1;
        lf -= 1;
    }
    for(int i=1;i<=n;i++) k -= marked[i];
    for(int i=1;i<=n;i++){
        if(marked[i]){
            printf("%d ", i);
            continue;
        }
        if(k){
            printf("%d ", i);
            k--;
        }
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'long long int query(long long int)':
sequence.cpp:21:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
sequence.cpp: In function 'int main()':
sequence.cpp:29: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:31: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: 29 / 29