제출 #964171

#제출 시각아이디문제언어결과실행 시간메모리
964171dubabuba수열 (APIO14_sequence)C++14
0 / 100
6 ms604 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> void ono_max(T &MAX, T CMP) { if(MAX < CMP) MAX = CMP; } const int mxk = 22; const int mxn = 1010; int dp[mxn][mxk], a[mxn], n; int ls[mxn][mxk], p[mxn], k; int main() { cin >> n >> k; if(n > mxn) return 1; for(int i = 1; i <= n; i++) { cin >> a[i]; p[i] = p[i - 1] + a[i]; } for(int i = 0; i < mxn; i++) for(int j = 0; j < mxk; j++) { if(j == 0) ls[i][j] = i; dp[i][j] = 1e9; } dp[1][0] = a[1] * a[1]; for(int cur = 2; cur <= n; cur++) for(int las = 1; las < cur; las++) { int las_sum = p[cur] - p[las]; for(int j = 0; j <= k && dp[las][j] != -1; j++) { int CMP = dp[las][j] + las_sum * las_sum; if(dp[cur][j + 1] > CMP) { dp[cur][j + 1] = CMP; ls[cur][j + 1] = las; } } } int t = (p[n] * p[n] - dp[n][k]) / 2; cout << t << endl; vector<int> v; for(int i = k; i >= 0; i--) { // cout << n << ' ' << i << endl; v.push_back(n); n = ls[n][i]; } while(v.size() > 1) { cout << v.back() << ' '; v.pop_back(); } 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...