제출 #30160

#제출 시각아이디문제언어결과실행 시간메모리
30160Andrei1998수열 (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; } } } int main() { //freopen("data.in", "r", stdin); cin >> N >> K; ++ K; for (int i = 1; i <= N; ++ i) { int val; cin >> val; sPart[i] = val + sPart[i - 1]; } brute(); cout << (1LL * sPart[N] * sPart[N] - dpBrute[K & 1][N]) / 2 << '\n'; vector <int> sol; int where = N; int k = K; while (father[k][where]) { sol.push_back(father[k][where]); where = father[k --][where]; } reverse(sol.begin(), sol.end()); for (int i = 0; i < sol.size(); ++ i) cout << sol[i] << " \n"[i + 1 == sol.size()]; return 0; }

컴파일 시 표준 에러 (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...