# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
312033 | 2020-10-12T07:54:32 Z | Rainbowbunny | Split the sequence (APIO14_sequence) | C++17 | 9 ms | 2688 KB |
#include <bits/stdc++.h> #define mp make_pair #define eb emplace_back #define fi first #define se second using namespace std; using cd = complex <double>; const int N = (1 << 20) + 5; const long long INF = 1e9; const int mod = 1e9 + 7;//1e9 + 7;//786433;//998244353; const double Pi = acos(-1); void Fastio() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n, k; long long s[100005]; long long dp[100005][2]; signed main() { Fastio(); cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> s[i]; s[i] += s[i - 1]; } for(int i = 1; i <= k; i++) { int pt = i - 1; for(int j = i; j <= n; j++) { while(dp[pt][i & 1 ^ 1] + (s[j] - s[pt]) * s[pt] < dp[pt + 1][i & 1 ^ 1] + (s[j] - s[pt + 1]) * s[pt + 1] and pt + 1 < j) { pt++; } dp[j][i & 1] = dp[pt][i & 1 ^ 1] + s[pt] * (s[j] - s[pt]); } } cout << dp[n][k & 1]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 384 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 384 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 384 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 384 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 640 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 2688 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |