제출 #977213

#제출 시각아이디문제언어결과실행 시간메모리
977213raspy수열 (APIO14_sequence)C++14
0 / 100
46 ms11480 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 }); } 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; } // cout << cht[k].first.m << " " << cht[k].first.c << "\n"; return 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]; } for (int i = 0; i <= k; i++) { cht.clear(); vstavi(0, 0, 0); for (int j = 1; j <= n; j++) { int x = getBestY(vs[j]); ndp[j] = dp[x] + (vs[j]-vs[x])*(vs[n]-vs[j]); // if (i == 0) // cout << j << " " << x << " " << ndp[j] << "\n"; par[i][j] = x; vstavi(vs[j], dp[j]-vs[j]*vs[n], j); } dp = ndp; } // for (int i = 1; i <= n; i++) // cout << dp[n] << "\n"; cout << dp[n] << "\n"; int tr = n; for (int i = k; i > 0; 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...