제출 #973129

#제출 시각아이디문제언어결과실행 시간메모리
973129oviyan_gandhi수열 (APIO14_sequence)C++17
89 / 100
534 ms82684 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int, int32_t> pii; #define N 100001 #define K 201 int ps[N], prv[N], curr[N]; int32_t dp[N][K]; struct Frac { int n, d; Frac(int num, int den) : n{num}, d{den} { if (d < 0) n = -n, d = -d; } bool operator < (const Frac &o) const { return __int128_t(n)*__int128_t(o.d) < __int128_t(o.n)*__int128_t(d); } }; struct Line { int m, c, i; Frac isect(const Line &o) const { return {c - o.c, o.m - m}; } int operator () (const int x) const { return m*x + c; } }; struct CHT { deque<Line> hull; void add(Line l){ while (hull.size() >= 2 && hull[1].isect(l) < hull[1].isect(hull[0])) hull.pop_front(); hull.push_front(l); } pii query(int x){ if (hull.empty()) return {0, 0}; while (hull.size() >= 2 && hull.back()(x) <= hull[hull.size()-2](x)) hull.pop_back(); return {hull.back()(x), hull.back().i}; } }; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++){ cin >> ps[i]; ps[i] += ps[i-1]; } ps[0] = -1; int ans = 0; for (int l = 1; l <= k; l++){ CHT hull; for (int i = 1; i <= n; i++){ auto [v, j] = hull.query(ps[i]); dp[i][l] = j; ans = curr[i] = v; if (i < n && ps[i] != ps[i+1]) hull.add({ps[i], prv[i] - ps[i]*ps[i], i}); } for (int i = 1; i <= n; i++) prv[i] = curr[i]; } cout << ans << '\n'; int curr = n; for (int i = k; i > 0; i--){ curr = dp[curr][i] ? dp[curr][i] : curr-1; assert(curr); cout << curr << ' '; } 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...