제출 #977227

#제출 시각아이디문제언어결과실행 시간메모리
977227raspy수열 (APIO14_sequence)C++14
0 / 100
46 ms10940 KiB
#include <iostream> #include <vector> #define inf 1'000'000'000'000'000'000 #define int long long #define EPS 0.0000001 using namespace std; struct ln { int m; int c; double p; }; int a[100005]; int vs[100005]; int par[205][100005]; vector<int> dp(100005); vector<int> ndp(100005); vector<pair<ln, int>> cht; double getx(int m1, int c1, int m2, int c2) { return (double)(c1-c2)/(m2-m1); } void vstavi(int m, int c, int ix) { double p = -inf; while (!cht.empty()) { p = getx(m, c, cht.back().first.m, cht.back().first.c); if (p <= cht.back().first.p-EPS) cht.pop_back(); else break; } cht.push_back({ {m, c, p}, ix }); } pair<int, int> getBestY(int x) { int k = 0; int L = 0, R = cht.size()- 1; while (L <= R) { int mid = (L+R) >> 1; if (cht[mid].first.p <= x+EPS) k = mid, L = mid+1; else R = mid-1; } return {cht[k].first.m*x+cht[k].first.c, cht[k].second}; } int32_t main() { int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; vs[i] = vs[i-1]+a[i]; } k++; for (int i = 1; i <= k; i++) { cht.clear(); vstavi(0, 0, 0); for (int j = 1; j <= n; j++) { pair<int, int> x = getBestY(vs[j]); ndp[j] = x.first + vs[j]*vs[n]-vs[j]*vs[j]; par[i][j] = x.second; vstavi(vs[j], dp[j]-vs[j]*vs[n], j); } dp = ndp; } int tr = n; cout << dp[tr] << "\n"; for (int i = k; i > 1; i--) { tr = par[i][tr]; cout << tr << " "; } cout << "\n"; return 0; }
#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...