제출 #23308

#제출 시각아이디문제언어결과실행 시간메모리
23308Nurlykhan수열 (APIO14_sequence)C++14
28 / 100
2000 ms25784 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define f first #define s second #define pb push_back #define mp make_pair #define ll long long #define ld long double #define sz(v) int(v.size()) #define all(v) v.begin(), v.end() using namespace std; const int N = (int) 1e4 + 7; const int M = (int) 2e6 + 7; const int K = 202; const ll LINF = (ll) 1e18; const int INF = (int) 1e9 + 7; const double EPS = (double) 1e-9; ll dp[N][K], a[N]; int p[N][K]; int n, k; ll sum(int l, int r) { return a[r] - a[l - 1]; } int main() { #define fn "balls" #ifdef witch freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else // freopen(fn".in", "r", stdin); // freopen(fn".out", "w", stdout); #endif cin >> n >> k; if (n == 1) { assert(0); } for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] += a[i - 1]; } for (int i = 1; i <= n; i++) { dp[i][1] = sum(1, i - 1) * sum(i, n); } for (int i = 2; i <= k; i++) { for (int j = i; j <= n; j++) { for (int t = 1; t < j; t++) { if (dp[j][i] < dp[t][i - 1] + sum(j, n) * sum(t, j - 1)) { dp[j][i] = dp[t][i - 1] + sum(j, n) * sum(t, j - 1); p[j][i] = t; } } } } int j = 1; for (int i = 1; i <= n; i++) { if (dp[j][k] < dp[i][k]) j = i; } cout << dp[j][k] << endl; vector<int> ans; while (j > 1 && k > 0) { ans.pb(j); j = p[j][k]; k--; } reverse(all(ans)); for (auto it : ans) cout << it - 1 << " "; 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...