제출 #537264

#제출 시각아이디문제언어결과실행 시간메모리
537264Sorting수열 (APIO14_sequence)C++17
38 / 100
436 ms131072 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 a__int128(x) (x).begin(), (x).end() struct CHT{ struct Line{ __int128 first, second; int index; Line(__int128 first, __int128 second, int index): first(first), second(second), index(index){} }; deque<Line> lines; __int128 floor_div3(__int128 a, __int128 b) { __int128 d = a / b; return d * b == a ? d : d - ((a < 0) ^ (b < 0)); } __int128 ip(Line l1, Line l2){ __int128 a = l1.second - l2.second; __int128 b = l2.first - l1.first; return floor_div3(a, b); } __int128 eval(Line l, __int128 x){ return l.first * x + l.second; } bool bad(__int128 k, __int128 b){ if(lines.back().first == k){ if(lines.back().second <= b) return true; return false; } return ip(lines[lines.size() - 2], lines.back()) > ip(lines.back(), Line(k, b, 0)); } void add(__int128 k, __int128 b, __int128 index){ while(lines.size() >= 2 && bad(k, b)) lines.pop_back(); lines.push_back(Line(k, b, index)); } pair<__int128, int> query(__int128 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 __int128 INF = 4e18; __int128 p[N]; ll a[N], n, k; __int128 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 << (ll)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...