제출 #915350

#제출 시각아이디문제언어결과실행 시간메모리
915350Pekiban수열 (APIO14_sequence)C++17
49 / 100
307 ms131072 KiB
#include <bits/stdc++.h> using namespace std; const int mxN = 1e5+2, mxK = 202; long long pref[mxN], dp[mxK][mxN], to[mxK][mxN], c, t, h[mxN]; long double cord(int x, int y) { return (long double)(dp[c][y] - pref[y]*pref[y] + pref[x]*pref[x] - dp[c][x])/(pref[x] - pref[y]); // deljenje 0-om? } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; for (int i = 1; i <= n; ++i) { int x; cin >> x; if (!x) { continue; } ++t; h[t] = i; pref[t] = pref[t-1] + x; } n = t; for (int i = 1; i <= k; ++i) { deque<int> dq = {0}; for (int j = 1; j <= n; ++j) { while (dq.size() > 1 && cord(dq[0], dq[1]) <= pref[j]) dq.pop_front(); dp[i][j] = pref[j]*pref[dq[0]] + dp[i-1][dq[0]] - pref[dq[0]]*pref[dq[0]]; to[i][j] = dq[0]; while (dq.size() > 1 && cord(dq[dq.size()-1], dq[dq.size()-2]) >= cord(dq[dq.size()-2], j)) dq.pop_back(); dq.push_back(j); } ++c; } // cout << '\n'; // for (int id = 0; id <= k; ++id) { // cout << id << ':'; // for (int i = 0; i <= n; ++i) { // cout << dp[id][i] << ' '; // } // cout << '\n'; // } cout << dp[k][n] << '\n'; vector<int> v = {n}; for (int i = k; i >= 1; --i) { v.push_back(to[i][v.back()]); } reverse(v.begin(), v.end()); v.pop_back(); for (auto i : v) cout << h[i] << ' '; }
#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...