Submission #1210501

#TimeUsernameProblemLanguageResultExecution timeMemory
1210501niepamietamhaslaSplit the sequence (APIO14_sequence)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e5 + 5; ll DP[MAXN][201]; int powrot[MAXN][201]; int A[MAXN]; int P[MAXN]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; for(int i = 1; i <= n; ++i){ cin >> A[i]; P[i] = P[i-1] + A[i]; } for(int i = 1; i <= n; ++i){ DP[i][1] = P[i] * P[i]; powrot[i][0] = -1; powrot[i][1] = -1; } powrot[0][0] = -1; powrot[0][1] = -1; DP[0][1] = 1e16; for(int l = 2; l <= k+1; ++l){ for(int i = 1; i <= n; ++i){ DP[i][l] = 1e16; for(int j = l-1; j < i; ++j){ if(DP[j][l-1] + (P[i] - P[j]) * (P[i] - P[j]) <= DP[i][l]){ DP[i][l] = DP[j][l-1] + (P[i] - P[j]) * (P[i] - P[j]); powrot[i][l] = j; } } } } cout << (P[n] * P[n] - DP[n][k+1]) / 2 << "\n"; vector<ll> ans; ll curr = n; ll ind = k+1; while(powrot[curr][ind] > 0){ //cout << curr << " " << ind << " " << powrot[curr][ind] << " pow\n"; ans.push_back(powrot[curr][ind]); curr = powrot[curr][ind]; ind--; } reverse(ans.begin(),ans.end()); for(auto u : ans){ cout << u << " "; } cout << "\n"; 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...