제출 #64758

#제출 시각아이디문제언어결과실행 시간메모리
64758leejseo수열 (APIO14_sequence)C++11
0 / 100
2029 ms132096 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' typedef long long lld; const static int MAXN = 100005; const static int MAXK = 205; int N, K, P[MAXN][MAXK]; lld S[MAXN], D[MAXN][MAXK]; void input(){ cin >> N >> K; for (int i=1; i<=N; i++){ cin >> S[i]; S[i] += S[i-1]; } } int DP(){ memset(D, -1, sizeof(D)); for (int i=1; i<=N; i++) D[i][0] = 0; for (int i=1; i<=N; i++){ for (int j=1; j<=min(K, i-1); j++){ int prev = -1; for (int k=1; k<i; k++){ if (D[k][j-1] == -1) continue; lld val = D[k][j-1] + S[k] * (S[i] - S[k]); if (val > D[i][j]){ prev = k; D[i][j] = val; } } P[i][j] = prev; } } return K; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); input(); int j = DP(); cout << D[N][j] << endl; vector<int> ans; int i = N; while (j > 0){ ans.push_back(P[i][j]); i = P[i][j]; j -= 1; } reverse(ans.begin(), ans.end()); for (auto &i : ans) cout << i << ' '; cout << endl; }
#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...