제출 #488146

#제출 시각아이디문제언어결과실행 시간메모리
488146ntabc05101수열 (APIO14_sequence)C++14
0 / 100
33 ms10492 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; for (int k = 1; k <= K; k++) { deq.clear(); deq.push_back(0); for (int i = 1; i <= n; i++) { while (deq.size() > 1 && slope(k - 1, deq[0], deq[1]) < a[i]) { deq.pop_front(); } int j = deq.front(); dp[i][k] = dp[j][k - 1] + (a[i] - a[j]) * a[j]; prf[i][k] = j; while (deq.size() > 1 && slope(k - 1, deq[deq.size() - 2], deq.back()) > slope(k - 1, deq.back(), i)) { deq.pop_back(); } deq.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...