제출 #746547

#제출 시각아이디문제언어결과실행 시간메모리
746547cscandkswon수열 (APIO14_sequence)C++17
89 / 100
1291 ms83812 KiB
#include <cstdio> #include <algorithm> using namespace std; int N, K, v, w; int A[100005]; long long S[100005]; long long D[100005][2]; int O[100005][205]; void dnc(int l, int r, int x, int y, int k) { if (l > r) return; int m = (l + r) >> 1; int i, p; long long q = 0; for (i = max(k - 1, x); i <= min(y, m - 1); i++) { if (q < (S[m] - S[i]) * (S[N] - S[m]) + D[i][w]) { q = (S[m] - S[i]) * (S[N] - S[m]) + D[i][w]; p = i; } } D[m][v] = q; O[m][k] = p; if (l == r) return; dnc(l, m - 1, x, p, k); dnc(m + 1, r, p, y, k); } void backtrack(int x, int k) { if (k == 0) return; backtrack(O[x][k], k - 1); printf("%d ", x); } int main() { int i, j, c = 0; scanf("%d %d", &N, &K); for (i = 1; i <= N; i++) scanf("%d", A + i); for (i = 1; i <= N; i++) S[i] = S[i - 1] + A[i]; for (i = 1; i <= N; i++) { D[i][0] = (S[i]) * (S[N] - S[i]); } v = 1, w = 0; // write on v, read on w for (i = 2; i <= K; i++) { for (j = 1; j <= N; j++) D[i][v] = 0; dnc(i, N - 1, 1, N - 1, i); swap(v, w); } int a = 0; for (i = K; i < N; i++) { if (D[i][w] > D[a][w]) a = i; } printf("%lld\n", D[a][w]); backtrack(a, K); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int main()':
sequence.cpp:37:15: warning: unused variable 'c' [-Wunused-variable]
   37 |     int i, j, c = 0;
      |               ^
sequence.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d %d", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:39:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     for (i = 1; i <= N; i++) scanf("%d", A + i);
      |                              ~~~~~^~~~~~~~~~~~~
sequence.cpp: In function 'void dnc(int, int, int, int, int)':
sequence.cpp:26:8: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |     dnc(l, m - 1, x, p, k);
      |     ~~~^~~~~~~~~~~~~~~~~~~
#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...