Submission #915374

#TimeUsernameProblemLanguageResultExecution timeMemory
915374PekibanSplit the sequence (APIO14_sequence)C++17
22 / 100
304 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], h[mxN], c, t, cnt; 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; vector<int> z; for (int i = 1; i <= n; ++i) { int x; cin >> x; if (!x) { z.push_back(i); continue; } ++t; h[t] = i; pref[t] = pref[t-1] + x; } n = t; if (n == 1) { cout << 0 << '\n'; for (int i = 1; i <= k; ++i) cout << i << ' '; return 0; } for (int i = 1; i <= k; ++i) { deque<int> dq = {1}; dp[i][1] = 0; for (int j = 2; 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 << dp[k][n] << '\n'; vector<int> v = {n}; for (int i = k; i >= 1 && to[i][v.back()]; --i) { v.push_back(to[i][v.back()]); cnt++; } reverse(v.begin(), v.end()); v.pop_back(); bitset<mxN> st; st.reset(); for (auto i : v) { cout << h[i] << ' '; st[h[i]] = 1; } for (int i = 1; i <= n && cnt < k; ++i) { if (!st[i]) { cout << i << ' '; cnt++; } } }
#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...