Submission #104503

#TimeUsernameProblemLanguageResultExecution timeMemory
104503E869120Split the sequence (APIO14_sequence)C++14
50 / 100
2033 ms36336 KiB
#include <iostream> #include <algorithm> #include <vector> using namespace std; long long N, K, A1[100009], A2[100009], dp[10009][209], pre[10009][209]; long long ranged(int l, int r) { long long V1 = A1[r] - A1[l - 1]; V1 *= V1; return V1; } long long solve() { for (int i = 0; i <= N; i++) { for (int j = 0; j <= K; j++) dp[i][j] = (1LL << 60); } dp[0][0] = 0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= K; j++) { for (int k = 0; k < i; k++) { long long cost = dp[k][j - 1] + ranged(k + 1, i); if (dp[i][j] > cost) { dp[i][j] = cost; pre[i][j] = k; } } } } return dp[N][K]; } int main() { cin >> N >> K; K++; for (int i = 1; i <= N; i++) { cin >> A1[i]; A2[i] = A1[i] * A1[i]; } for (int i = 1; i <= N; i++) { A1[i] += A1[i - 1]; A2[i] += A2[i - 1]; } cout << (ranged(1, N) - solve()) / 2LL << endl; vector<int>T; int cx = N, cy = K; while (cy >= 1) { if (cy < K) T.push_back(cx); cx = pre[cx][cy]; cy--; } for (int i = T.size() - 1; i >= 0; i--) { cout << T[i]; if (i) cout << " "; } cout << endl; return 0; }
#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...