제출 #636855

#제출 시각아이디문제언어결과실행 시간메모리
636855elkernos수열 (APIO14_sequence)C++17
71 / 100
64 ms131072 KiB
#include <bits/stdc++.h> using namespace std; #define int long long struct L { int a, b, from; int operator()(int x) { return a * x + b; } pair<int, int> inter(L &he) const { int up = he.b - b; int down = a - he.a; return {up, down}; } }; struct CHT { vector<L> hull; int start = 0; pair<int, int> query(int x, int i) { while(start <= (int)hull.size() - 2) { L A = hull[start], B = hull[start + 1]; if(B.from < i && A(x) <= B(x)) start++; else break; } return {hull[start](x), hull[start].from}; } void add(L x) { if(!hull.empty() && hull.back().a == x.a) { if(hull.back().b < x.b) { hull.pop_back(); } else { return; } } while(start <= (int)hull.size() - 2) { L A = hull.end()[-2], B = hull.end()[-1]; auto one = A.inter(B), two = B.inter(x); if(one.first * two.second > two.first * one.second) { hull.pop_back(); } else { break; } } hull.push_back(x); } }; int sq(int x) { return x * x; } int32_t main() { cin.tie(0)->sync_with_stdio(0); int n, k; cin >> n >> k; vector<int> p(n + 1); for(int i = 1; i <= n; i++) { cin >> p[i]; p[i] += p[i - 1]; } CHT dp; for(int i = 1; i <= n; i++) { dp.add({p[i], -sq(p[i]), i}); } vector<vector<int>> come(k + 1, vector<int>(n + 1)); for(int now = 1; now <= k; now++) { CHT new_dp; for(int i = now + 1; i <= n; i++) { auto in = dp.query(p[i], i); if(now == k && i == n) { cout << in.first << '\n'; } come[now][i] = in.second; if(i < n) { new_dp.add({p[i], in.first - sq(p[i]), i}); } } dp = new_dp; } vector<int> print(k); int nn = n, kk = k; while(kk) { nn = come[kk][nn]; kk--; print[kk] = nn; } for(int i = 0; i < k; i++) { cout << print[i] << " "; } cout << '\n'; }
#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...