제출 #973013

#제출 시각아이디문제언어결과실행 시간메모리
973013oviyan_gandhi수열 (APIO14_sequence)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int, int> pii; #define N 100001 #define K 201 int ps[N]; pii 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; return n == 1; for (int i = 1; i <= n; i++){ cin >> ps[i]; ps[i] += ps[i-1]; } CHT prv; for (int i = 1; i <= n; i++){ if (ps[i] == ps[i-1]) continue; prv.add({ps[i], -ps[i]*ps[i], i}); } for (int l = 1; l <= k; l++){ CHT curr; for (int i = 1; i <= n; i++){ if (ps[i] == ps[i-1]) continue; dp[i][l] = prv.query(ps[i]); curr.add({ps[i], dp[i][l].first - ps[i]*ps[i], i}); } prv = curr; } cout << dp[n][k].first << '\n'; int curr = n; for (int i = k; i > 0; i--){ cout << dp[curr][i].second << ' '; curr = dp[curr][i].second; } 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...