# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
875975 | 2023-11-21T01:14:28 Z | rukashii | Split the sequence (APIO14_sequence) | C++17 | 133 ms | 3060 KB |
#include <bits/stdc++.h> using namespace std; #define file if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } #define int long long void setIn(string s) { freopen(s.c_str(),"r",stdin); } void setOut(string s) { freopen(s.c_str(),"w",stdout); } void setIO(string s = "") { if (s.size()) setIn(s+".in"), setOut(s+".out"); } const int maxn = 1e5 + 2, maxk = 202; int a[maxn], prf[maxn], n, k; namespace Sub2 { const int s2maxn = 52, s2maxk = 52; int dp[s2maxn][s2maxn][s2maxk]; int cal(int l, int r, int krem) { if (l == r || krem == 0) return dp[l][r][krem] = 0; int res = dp[l][r][krem]; if (res != -1) return res; res = 0; for (int i = l; i < r; i++) { for (int lk = 0; lk < krem; lk++) { int rk = krem - lk - 1; res = max(res, cal(l, i, lk) + cal(i + 1, r, rk) + (prf[r] - prf[i]) * (prf[i] - prf[l - 1])); } } return dp[l][r][krem] = res; } void trace(int l, int r, int krem) { bool skip = 0; for (int i = l; i < r; i++) { for (int lk = 0; lk < krem; lk++) { int rk = krem - lk - 1; if (dp[l][r][krem] == cal(l, i, lk) + cal(i + 1, r, rk) + (prf[r] - prf[i]) * (prf[i] - prf[l - 1])) { cout << i << ' '; trace(1, i, lk); trace(i + 1, r, rk); skip = 1; break; } } if (skip) break; } } void solve() { memset(dp, -1, sizeof(dp)); cout << cal(1, n, k) << '\n'; trace(1, n, k); } } namespace Sub4 { const int s4maxn = 1002, s4maxk = 202; int dp[s4maxn][s4maxk]; void solve() { dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { for (int p = 0; p < i; p++) { dp[i][j] = max(dp[p][j - 1] * (prf[i] - prf[p]), dp[i][j]); } } } cout << dp[n][k]; } } signed main() { // setIO(); file; ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i], prf[i] = prf[i - 1] + a[i]; if (n <= 50) return Sub2::solve(), 0; // if (n <= 1000) // return Sub4::solve(), 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2904 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 999 == 999 |
3 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 0 == 0 |
4 | Correct | 1 ms | 2768 KB | contestant found the optimal answer: 1542524 == 1542524 |
5 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 4500000000 == 4500000000 |
6 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 1 == 1 |
7 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 1 == 1 |
8 | Correct | 1 ms | 2904 KB | contestant found the optimal answer: 1 == 1 |
9 | Correct | 1 ms | 2904 KB | contestant found the optimal answer: 100400096 == 100400096 |
10 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 900320000 == 900320000 |
11 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 3698080248 == 3698080248 |
12 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 3200320000 == 3200320000 |
13 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 140072 == 140072 |
14 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 376041456 == 376041456 |
15 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 805 == 805 |
16 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 900189994 == 900189994 |
17 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 999919994 == 999919994 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 3060 KB | contestant found the optimal answer: 1093956 == 1093956 |
2 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 302460000 == 302460000 |
3 | Correct | 133 ms | 2956 KB | contestant found the optimal answer: 122453454361 == 122453454361 |
4 | Correct | 1 ms | 2908 KB | contestant found the optimal answer: 93663683509 == 93663683509 |
5 | Correct | 5 ms | 2908 KB | contestant found the optimal answer: 1005304678 == 1005304678 |
6 | Correct | 3 ms | 2732 KB | contestant found the optimal answer: 933702 == 933702 |
7 | Correct | 34 ms | 2908 KB | contestant found the optimal answer: 25082842857 == 25082842857 |
8 | Correct | 6 ms | 2904 KB | contestant found the optimal answer: 687136 == 687136 |
9 | Correct | 3 ms | 2908 KB | contestant found the optimal answer: 27295930079 == 27295930079 |
10 | Correct | 11 ms | 2976 KB | contestant found the optimal answer: 29000419931 == 29000419931 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 344 KB | Unexpected end of file - int64 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Unexpected end of file - int64 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 604 KB | Unexpected end of file - int64 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 2140 KB | Unexpected end of file - int64 expected |
2 | Halted | 0 ms | 0 KB | - |