Submission #23469

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

sequence

/* Bismillahir Rahmanir Rahim */
 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 100005;
const int K = 205;
 
vector<long long>M, B, id;
int 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]);
}
 
inline void add(long long m, long long b, int i){
    M.push_back(m);
    B.push_back(b);
    id.push_back(i);
    while(M.size() >= 3 && bad(M.size()-3, M.size()-2, M.size()-1)){
        M.erase(M.end()-2);
        B.erase(B.end()-2);
        id.erase(id.end()-2);
    }
}
 
inline long long query(long long x){
    if(ptr >= M.size()) ptr = M.size() - 1;
    while(ptr + 1 < M.size() && 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++){
        M.clear();
        B.clear();
        id.clear();
        ptr = 0;
        add(sum[1], -(sum[1] * sum[1]), 1);
        for(int i=2;i<=n;i++){
            cur[i] = query(sum[i]);
            nxt[i][j] = id[ptr];
            add(sum[i], -(sum[i] * sum[i]) + past[i], i);
        }
        for(int i=1;i<=n;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 'long long int query(long long int)':
sequence.cpp:29:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ptr >= M.size()) ptr = M.size() - 1;
            ^
sequence.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr + 1 < M.size() && M[ptr+1] * x + B[ptr+1] > M[ptr] * x + B[ptr]){
                   ^
sequence.cpp: In function 'int main()':
sequence.cpp:42: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:44: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