제출 #491466

#제출 시각아이디문제언어결과실행 시간메모리
491466Mondeus수열 (APIO14_sequence)C++17
0 / 100
89 ms88796 KiB
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <set> #include <cassert> #include <algorithm> using namespace std; struct CHT { vector<long long> a; vector<long long> b; vector<long long> id; bool cross(int i, int j, int k) { return 1.d*(b[k] - b[i]) * (a[j] - a[i]) >= 1.d*(b[j] - b[i]) * (a[k] - a[i]); } void add(long long A, long long B, long long ID) { a.push_back(A); b.push_back(B); id.push_back(ID); while(a.size() > 2 && cross(a.size()-3,a.size()-2,a.size()-1)) { a.erase(a.end()-2); b.erase(b.end()-2); id.erase(id.end()-2); } } pair<long long, long long> query(long long x) { if(a.size()==0) return {0,0}; int l = 0, r = a.size()-1; while(l < r) { int mid = (l+r)/2; long long f1 = a[mid] * x + b[mid]; long long f2 = a[mid+1] * x + b[mid+1]; if(f1 > f2) r = mid; else l = mid+1; } return {a[l] * x + b[l], id[l]}; } }; long long a[100005]; int pre[100005][205]; CHT hull[205]; int n,k; void solve() { cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) a[i] += a[i-1]; long long v = 0; for(int i = 1; i <= n; i++) { for(int j = min(i,k+1); j >= 1; j--) { auto calc = hull[j-1].query(a[i]); pre[i][j] = calc.second; hull[j].add(a[i],calc.first - a[i] * a[i], i); v = calc.first; } } cout << v << '\n'; int cnt = k + 1; int step = n; vector<int> ans; while(cnt > 1) { step = pre[step][cnt]; cnt--; ans.push_back(step); } reverse(ans.begin(),ans.end()); for(auto x: ans) cout << x << ' '; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); solve(); 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...