This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 j = 1; j <= k+1; j++)
{
for(int i = 1; i <= n; i++)
{
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);
if(j==k+1 && i==n) 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |