제출 #488141

#제출 시각아이디문제언어결과실행 시간메모리
488141ntabc05101수열 (APIO14_sequence)C++14
0 / 100
26 ms11664 KiB
#include<bits/stdc++.h> using namespace std; #define taskname "" const long long inf = 1e17; int main() { if (fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } else { if (fopen(taskname".in", "r")) { freopen(taskname".in", "r", stdin); freopen(taskname".out", "w", stdout); } } cin.tie(0)->sync_with_stdio(0); int n, K; cin >> n >> K; long long a[n + 1]; a[0] = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] += a[i - 1]; } vector<long long> dp[n + 1]; function<long double(int, int, int)> slope = [&](int k, int i, int j) { return (long double)(dp[i][k] - a[i] * a[i] - dp[j][k] + a[j] * a[j]) / (a[j] - a[i]); }; K++; int prf[n + 1][K + 1]; memset(prf, 0, sizeof(prf)); long long res = 0; for (int i = 0; i <= n; i++) { dp[i].assign(K + 1, -inf); } dp[0][0] = 0; deque<int> deq[K + 1]; for (int i = 0; i <= K; i++) { deq[i].clear(); } deq[0].push_back(0); for (int i = 1; i <= n; i++) { for (int k = 1; k <= K; k++) { while (deq[k - 1].size() > 1 && slope(k - 1, deq[k - 1][0], deq[k - 1][1]) < a[i]) { deq[k - 1].pop_front(); } if (deq[k - 1].empty()) { continue; } int j = deq[k - 1].front(); dp[i][k] = dp[j][k - 1] + (a[i] - a[j]) * a[j]; prf[i][k] = j; } for (int k = 1; k <= K; k++) { while (deq[k].size() > 1 && slope(k, deq[k][deq[k].size() - 2], deq[k].back()) > slope(k, deq[k].back(), i)) { deq[k].pop_back(); } deq[k].push_back(i); } } cout << dp[n][K] << "\n"; while (K > 1) { cout << prf[n][K] << " "; n = prf[n][K--]; } cout << "\n"; return 0; } /* 7 3 4 1 3 4 0 2 3 */

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

sequence.cpp: In function 'int main()':
sequence.cpp:37:12: warning: unused variable 'res' [-Wunused-variable]
   37 |  long long res = 0;
      |            ^~~
sequence.cpp:10:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:11:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:15:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |    freopen(taskname".in", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:16:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |    freopen(taskname".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...