Submission #299190

#TimeUsernameProblemLanguageResultExecution timeMemory
299190AaronNaiduSplit the sequence (APIO14_sequence)C++14
11 / 100
2033 ms131072 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[250][250][250]; pair<ll, ll> dpAns[250][250][250]; ll n, k; ll nums[2000]; ll prefSum[2000]; void explore(int s, int f, int regions) { if (regions == 0) { return; } ll split = dpAns[s][f][regions].first; ll reg = dpAns[s][f][regions].second; //cout << "Exploring " << s << " " << f << " " << regions << "\n"; //cout << "Answer is " << split << " " << reg << "\n"; cout << split << " "; explore(s, split, reg); explore(split+1, f, regions - reg - 1); } ll getDP(int s, int f, int regions) { if (regions > f-s) { return -1000000000000; } if (regions == 0) { return 0; } if (dp[s][f][regions] >= 0) { return dp[s][f][regions]; } ll cand = 0; for (int i = s; i < f; i++) { ll thisCand = (prefSum[i] - prefSum[s-1]) * (prefSum[f] - prefSum[i]); ll maxLittleCand = -1; ll thisLeftRegions = 0; for (int j = 0; j <= min(i-s, regions-1); j++) { ll thisLittleCand = getDP(s, i, j) + getDP(i+1, f, regions-j-1); if (maxLittleCand < thisLittleCand) { maxLittleCand = max(maxLittleCand, thisLittleCand); thisLeftRegions = j; } } thisCand += maxLittleCand; if (thisCand >= cand) { cand = max(cand, thisCand); dpAns[s][f][regions] = {i, thisLeftRegions}; } } return cand; } int main() { cin >> n >> k; cin >> nums[1]; prefSum[1] = nums[1]; prefSum[0] = 0; for (int i = 1; i < n; i++) { cin >> nums[i+1]; prefSum[i+1] = prefSum[i] + nums[i+1]; } for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { for (int k = 0; k <= n; k++) { dp[i][j][k] = -1; } } } ll ans = getDP(1, n, k); cout << ans << "\n"; explore(1, n, k); //cout << "\b\n"; }
#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...