Submission #23467

#	Time	Username	Problem	Language	Result	Execution time	Memory
23467		rubabredwan	Split the sequence (APIO14_sequence)	C++14	60 / 100	2000 ms	88904 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]);
}

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);
    }
}

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 cur[N], past[N];
int fk[N][K];
long long A[N], sum[N];
int n, k;

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]);
            fk[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;
    while(k){
        cout << fk[n][k] << ' ';
        n = fk[n][k];
        k = k - 1;
    }
    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: 0 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29