Submission #23166

#TimeUsernameProblemLanguageResultExecution timeMemory
23166ruhanhabib39Split the sequence (APIO14_sequence)C++14
0 / 100
13 ms91876 KiB
#include <bits/stdc++.h> using namespace std; typedef long long Long; const int MAXN = 1e5; const int MAXK = 200; int N, K; Long A[MAXN + 10], S[MAXN + 10]; Long dp[2][MAXN + 10]; int pos[MAXK + 10][MAXN + 10]; struct dat { Long m, b; int i; Long f(Long x) const { return m*x + b; } }; bool bad(dat l1, dat l2, dat l3) { return (l1.b - l2.b)*(l3.m - l1.m) > (l1.b - l3.b)*(l2.m - l1.m); } vector<dat> L; void add(dat l) { L.push_back(l); while(L.size() >= 3 && bad(L[L.size()-3], L[L.size()-2], L[L.size()-1])) { L.erase(L.end() - 2); } } int ii = 0; int get(Long x) { if(ii >= (int)L.size()) ii = L.size()-1; while(ii+1 < (int)L.size() && L[ii+1].f(x) > L[ii].f(x)) { ii++; } return L[ii].i; } void add(int x, int j) { Long m = S[j]; Long b = - S[j] * S[j] + dp[x][j]; add(dat{m, b, j}); } void calc_dp() { for(int k = 1; k <= K; k++) { int x = k & 1; L.clear(); ii = 0; if(k > 0) add(x ^ 1, k-1); for(int i = k; i <= N; i++) { int j = get(S[i]); pos[k][i] = j; dp[x][i] = S[j]*S[i] - S[j]*S[j] + dp[x^1][j]; add(x ^ 1, i); } } } int main() { scanf("%d%d", &N, &K); S[0] = 0; for(int i = 1; i <= N; i++) { scanf("%lld", &A[i]); S[i] = A[i] + S[i-1]; } calc_dp(); printf("%lld\n", dp[K&1][N]); int i = N, k = K; while(k > 0) { i = pos[k][i]; printf("%d ", i); k--; } printf("\n"); }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:66:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &N, &K);
                         ^
sequence.cpp:69:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld", &A[i]);
                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...