Submission #1255243

#TimeUsernameProblemLanguageResultExecution timeMemory
1255243duybinhbeoSplit the sequence (APIO14_sequence)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; int dp[20][20]; int a[20]; int b[20]; int trace[20][20]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n,k; cin >> n >> k; for (int i = 1; i <= n; ++i){ cin >> a[i]; b[i]=b[i-1]+a[i]; } for (int j = 2; j <= k+1; ++j){ for (int i = 1; i <= n; ++i){ for (int q = 1; q < i; ++q){ if (dp[i][j] < dp[q][j-1]+b[q]*(b[i]-b[q])){ dp[i][j] = max(dp[i][j],dp[q][j-1]+b[q]*(b[i]-b[q])); trace[i][j] = q; } } } } cout << dp[n][k+1] << '\n'; int d = k+1,u = n; vector<int>ans; while (d > 1){ ans.push_back(trace[u][d]); u = trace[u][d]; --d; } reverse(ans.begin(),ans.end()); for (int i : ans) cout << i << ' '; }
#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...