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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define MAXK 205
const ll INF = 1e18;
struct line {ll n;ll k;int id;};
double presekx(line a,line b)
{
if(a.k==b.k)return INF;
return (a.n-b.n)/(b.k-a.k);
}
ll dp[MAXK][MAXN];
ll a[MAXN];
int opt[MAXK][MAXN];
deque <line> q;
line next_front()
{
line a = q.front();
q.pop_front();
line b = q.front();
q.push_front(a);
return b;
}
line prev_back()
{
line a = q.back();
q.pop_back();
line b = q.back();
q.push_back(a);
return b;
}
ll eval(line l,ll x)
{
return l.k*x+l.n;
}
int main()
{
ios_base::sync_with_stdio(false);
int n,k;
cin >> n >> k;
for(int i = 1; i <= n; i++)cin >> a[i],a[i]+=a[i-1];
for(int i = 1; i <= k; i++)
{
q.clear();
for(int j = i; j <= n; j++)
{
while(1)
{
if(q.size()<=1)break;
if(eval(q.front(),a[j])<=eval(next_front(),a[j])){q.pop_front();continue;}
break;
}
if(q.size())
{
dp[i][j]=eval(q.front(),a[j]);
opt[i][j]=q.front().id;
}
line add;
add.k=a[j];
add.n=-a[j]*a[j]+dp[i-1][j];
add.id=j;
while(1)
{
if(q.size()<=1)break;
if(q.back().k==add.k){q.pop_back();continue;}
if(q.back().k==prev_back().k){q.pop_back();continue;}
if(presekx(prev_back(),q.back())>=presekx(q.back(),add)){q.pop_back();continue;}
break;
}
q.push_back(add);
}
}
cout << dp[k][n] << "\n";
int now = n;
while(k > 0)
{
cout << opt[k][now] << " ";
now=opt[k][now];
k--;
}
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... |