제출 #973086

#제출 시각아이디문제언어결과실행 시간메모리
973086oviyan_gandhi수열 (APIO14_sequence)C++17
89 / 100
685 ms84816 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]; 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){ 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; CHT prv; for (int i = 1; i <= n; i++) if (ps[i] != ps[i-1]) prv.add({ps[i], -ps[i]*ps[i], i}); int ans = 0; for (int l = 1; l <= k; l++){ CHT curr; for (int i = 1; i <= n; i++){ if (ps[i] == ps[i-1]) continue; auto [v, j] = prv.query(ps[i]); dp[i][l] = j; ans = v; curr.add({ps[i], v - ps[i]*ps[i], i}); } prv = curr; } cout << ans << '\n'; int curr = n; for (int i = k; i > 0; i--){ while (ps[curr] == ps[curr-1]) curr--; cout << min(dp[curr][i], int32_t(n-1)) << ' '; curr = dp[curr][i]; } 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...