제출 #395783

#제출 시각아이디문제언어결과실행 시간메모리
395783kaplanbar수열 (APIO14_sequence)C++14
0 / 100
2075 ms131076 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<ll> v(n); for(int i = 0; i < n; i++) cin >> v[i]; vector<ll> pre(n); for(int i = 0; i < n; i++) { pre[i] = v[i]; if(i) pre[i] += pre[i - 1]; } auto get_sum = [&](int l, int r) -> ll { ll ret = pre[r]; if(l) ret -= pre[l - 1]; return ret; }; vector<vector<ll>> dp(n, vector<ll>(k + 1, -1e9)); vector<vector<int>> from(n, vector<int>(k + 1, -1)); for(int i = 0; i < n; i++) dp[i][0] = 0; for(int i = 0; i < n; i++) { for(int j = 1; j <= k; j++) { int l = 0, r = i - 1; for(int c = 0; c < 300; c++) { int mid1 = (l + l + r) / 3, mid2 = (l + r + r) / 3; ll val1 = dp[mid1][j - 1] + get_sum(0, mid1) * get_sum(mid1 + 1, i); ll val2 = dp[mid2][j - 1] + get_sum(0, mid2) * get_sum(mid2 + 1, i); if(val1 < val2) l = mid1; else r = mid2; } for(int h = l; h <= r; h++) { if(dp[h][j - 1] == -1e9) continue; ll val = dp[h][j - 1] + get_sum(0, h) * get_sum(h + 1, i); if(val >= dp[i][j]) { from[i][j] = h; dp[i][j] = val; } } // for(int t = i; t >= 1; t--) { // dp[i][j] = max(dp[i][j], (dp[t - 1][j - 1] + get_sum(0, t - 1) * get_sum(t, i))); // } } } cout << dp[n - 1][k] << "\n"; vector<int> ans; int cur = n - 1, curk = k; while(curk) { cur = from[cur][curk]; ans.push_back(cur); curk--; } reverse(ans.begin(), ans.end()); for(int x : ans) cout << x + 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...