제출 #536699

#제출 시각아이디문제언어결과실행 시간메모리
536699Sorting수열 (APIO14_sequence)C++17
0 / 100
12 ms5268 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; } template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; } #define all(x) (x).begin(), (x).end() struct CHT{ struct Line{ ll first, second; int index; Line(ll first, ll second, int index): first(first), second(second), index(index){} }; deque<Line> lines; ll floor_div(ll a, ll b){ if((a < 0) ^ (b < 0)) return a / b - !!(a % b); return a / b; } ll ip(Line l1, Line l2){ ll a = l1.second - l2.second; ll b = l2.first - l1.first; return floor_div(a, b); } ll eval(Line l, ll x){ return l.first * x + l.second; } void add(ll k, ll b, ll index){ while(lines.size() >= 2 && ip(lines[lines.size() - 2], lines.back()) >= ip(lines.back(), Line(k, b, index))) lines.pop_back(); lines.push_back(Line(k, b, index)); } pair<ll, int> query(ll x){ while(lines.size() >= 2 && eval(lines[0], x) <= eval(lines[1], x)) lines.pop_front(); return {eval(lines.front(), x), lines.front().index}; } }; const int N = 1e5 + 3; const int K = 200 + 3; const ll INF = 4e18; ll a[N], n, p[N], k; ll dp[K][N]; int pr[K][N]; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; ++k; for(int i = 1; i <= n; ++i) cin >> a[i]; for(int i = 1; i <= n; ++i) p[i] = p[i - 1] + a[i]; for(int i = 1; i <= n; ++i) dp[0][i] = -INF; dp[0][n + 1] = 0; for(int j = 1; j <= k; ++j){ CHT cht; for(int i = n; i >= 1; --i){ cht.add(-p[i], -p[i] * p[i] + p[i] * p[n] + dp[j - 1][i + 1], i); auto q = cht.query(-p[i - 1]); dp[j][i] = q.first - p[i - 1] * p[n]; pr[j][i] = q.second; } dp[j][n + 1] = -INF; } cout << dp[k][1] << "\n"; int pos = 1; while(k > 1){ int index = pr[k][pos]; cout << index << " "; pos = index + 1; --k; } cout << "\n"; } /* 7 3 4 1 3 4 0 2 3 */
#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...