Submission #112906

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
1129062019-05-22 15:07:33AkashiSplit the sequence (APIO14_sequence)C++14
100 / 100
1388 ms80888 KiB
#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()
{
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &K);
     ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:35:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n ; ++i) scanf("%d", &S[i]), S[i] += S[i - 1];
                                  ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
#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...