Submission #23462

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

sequence

/* Bismillahir Rahmanir Rahim */
 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 10005;
const int K = 205;
 
vector<long long>M, B;
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){
    M.push_back(m);
    B.push_back(b);
    while(M.size() >= 3 && bad(M.size()-3, M.size()-2, M.size()-1)){
        M.erase(M.end()-2);
        B.erase(B.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 dp[N][K], 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();
        ptr = 0;
        add(sum[1], -(sum[1] * sum[1]));
        for(int i=2;i<=n;i++){
            dp[i][j] = query(sum[i]);
            add(sum[i], -(sum[i] * sum[i]) + dp[i][j-1]);
        }
    }
    cout << dp[n][k] << endl;
    while(k){
        for(int div = n-1;div >= 1;div--){
            long long add = sum[div] * sum[n] - sum[div] * sum[div];
            if(dp[div][k-1] + add == dp[n][k]){
                cout << div << ' ';
                n = div;
                break;
            }
        }
        k--;
    }
    cout << endl;
	return 0;
}
 

Compilation message (stderr)

sequence.cpp: In function 'long long int query(long long int)':
sequence.cpp:27:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ptr >= M.size()) ptr = M.size() - 1;
            ^
sequence.cpp:28: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:38: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:40: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