Submission #1133510

#TimeUsernameProblemLanguageResultExecution timeMemory
1133510finalventureSplit the sequence (APIO14_sequence)C++17
22 / 100
4 ms840 KiB
#include <bits/stdc++.h> using namespace std; int main() { iostream::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; } vector<long long> prefixSum(n + 1, 0); for (int i = 1; i <= n; ++i) { prefixSum[i] = prefixSum[i - 1] + a[i]; } vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0)); vector<vector<int>> splits(n + 1, vector<int>(k + 1, -1)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= min(i - 1, k); ++j) { dp[i][j] = LLONG_MIN; // Iterate through possible split points for (int k = 1; k < i; ++k) { long long points = (prefixSum[k]) * (prefixSum[i] - prefixSum[k]); long long totalPoints = dp[k][j - 1] + points; if (totalPoints > dp[i][j]) { dp[i][j] = totalPoints; splits[i][j] = k; // Store the split position } } } } cout << dp[n][k] << endl; vector<int> splitPositions; int cur_n = n, cur_k = k; while (cur_k > 0) { int splitPos = splits[cur_n][cur_k]; splitPositions.push_back(splitPos); cur_n = splitPos; cur_k--; } // Print split positions in reverse order for (int i = splitPositions.size() - 1; i >= 0; --i) { cout << splitPositions[i] << " "; } 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...