Submission #23248

#TimeUsernameProblemLanguageResultExecution timeMemory
23248NurlykhanSplit the sequence (APIO14_sequence)C++14
0 / 100
19 ms9832 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define f first #define s second #define pb push_back #define mp make_pair #define ll long long #define ld long double #define sz(v) int(v.size()) #define all(v) v.begin(), v.end() using namespace std; const int N = (int) 100; const int M = (int) 2e6 + 10; const ll LINF = (ll) 1e18; const int INF = (int) 1e9 + 7; const double EPS = (double) 1e-9; int n, k; ll dp[N][N][N]; int a[N]; int sum(int l, int r) { return a[r] - a[l - 1]; } int get_id(int l, int r) { int ans = l; for (int i = l; i < r; i++) { if (sum(l, ans) * 1ll * sum(ans + 1, r) < sum(l, i) * 1ll * sum(i + 1, r)) ans = i; } return ans; } ll calc(int l, int r, int k); ll f(int l, int r, int k, int i) { return calc(l, i, k - 1) + sum(l, i) * 1ll * sum(i + 1, r); } ll f1(int l, int r, int k, int i) { return calc(i + 1, r, k - 1) + sum(l, i) * 1ll * sum(i + 1, r); } int ptr[N], ptr1[N]; ll calc(int l, int r, int k) { if (l > r) return 0; if (k == 0) return 0; ll &ans = dp[l][r][k]; if (ans != -1) return ans; ans = 0; ptr[l] = max(ptr[l], l); ptr1[l] = max(ptr1[l], l); while (ptr[l] + 1 < r && f(l, r, k, ptr[l]) <= f(l, r, k, ptr[l] + 1)) ptr[l]++; while (ptr1[l] + 1 < r && f1(l, r, k, ptr1[l]) <= f1(l, r, k, ptr1[l] + 1)) ptr1[l]++; ans = max(f(l, r, k, ptr[l]), f1(l, r, k, ptr1[l])); return ans; } void print(int l, int r, int k) { if (k == 0) return; for (int i = l; i < r; i++) { for (int t = 0; t <= 0; t++) { if (calc(l, r, k) == calc(l, i, t) + calc(i + 1, r, k - 1 - t) + sum(l, i) * 1ll * sum(i + 1, r)) { cout << i << " "; print(l, i, t); print(i + 1, r, k - 1 - t); return; } } for (int t = k - 1; t < k; t++) { if (calc(l, r, k) == calc(l, i, t) + calc(i + 1, r, k - 1 - t) + sum(l, i) * 1ll * sum(i + 1, r)) { cout << i << " "; print(l, i, t); print(i + 1, r, k - 1 - t); return; } } } } int main() { #define fn "balls" #ifdef witch freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else // freopen(fn".in", "r", stdin); // freopen(fn".out", "w", stdout); #endif memset(dp, -1, sizeof(dp)); cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] += a[i - 1]; } cout << calc(1, n, k) << endl; print(1, n, k); 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...