Submission #30160

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
301602017-07-22 17:58:43Andrei1998Split the sequence (APIO14_sequence)C++14
0 / 100
0 ms1844 KiB
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100000 + 5;
const int KMAX = 200 + 5;
typedef long long int lint;
const lint INF = 2E18;
int N, K;
int sPart[NMAX];
lint dpBrute[KMAX][NMAX];
int father[KMAX][NMAX];
void brute() {
dpBrute[1][0] = INF;
for (int j = 1; j <= N; ++ j)
dpBrute[1][j] = 1LL * sPart[j] * sPart[j];
for (int i = 2; i <= K; ++ i) {
dpBrute[i & 1][0] = INF;
for (int j = 1; j <= N; ++ j) {
pair <lint, int> sol = {1LL * (sPart[j] - sPart[j - 1]) * (sPart[j] - sPart[j - 1]) + dpBrute[(i - 1) & 1][j - 1], j - 1};
for (int k = 1; k <= j; ++ k)
sol = min(sol, {1LL * (sPart[j] - sPart[k - 1]) * (sPart[j] - sPart[k - 1]) + dpBrute[(i - 1) & 1][k - 1], k - 1});
dpBrute[i & 1][j] = sol.first;
father[i][j] = sol.second;
}
}
}
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < sol.size(); ++ i)
                       ^
sequence.cpp:57:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         cout << sol[i] << " \n"[i + 1 == sol.size()];
                                       ^
#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...