# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
112906 | Akashi | Split the sequence (APIO14_sequence) | C++14 | 1388 ms | 80888 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n, K;
int S[100005];
int which[205][100005];
long long DP[2][100005];
long long *Last, *Now;
void divide(int k, int L, int R, int whL, int whR){
int mid = (L + R) >> 1;
for(int j = whL; j <= whR && j <= mid ; ++j){
long long aux = Last[j - 1] + 1LL * (S[mid] - S[j - 1]) * (S[n] - S[mid]);
if(aux > Now[mid]) Now[mid] = aux, which[k][mid] = j;
}
if(L < R){
divide(k, L, mid - 1, whL, which[k][mid]);
divide(k, mid + 1, R, which[k][mid], whR);
}
}
void solve(int n, int k){
if(k == 1) return ;
solve(which[k][n] - 1, k - 1);
printf("%d ", which[k][n] - 1);
}
int main()
{
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |