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;
#define MAXN 100005
#define MAXK 205
typedef long long ll;
ll dp[MAXN][MAXK];
ll s[MAXN];
int opt[MAXN][MAXK];
struct lajn
{
ll k;
ll n;
int idx;
};
ll f(lajn a,ll x)
{
return a.k*x+a.n;
}
bool bad(lajn a,lajn b,lajn c)
{
return (a.n-b.n)*(c.k-b.k) <= (b.n-c.n)*(b.k-a.k);
}
lajn prev_back(deque <lajn> q)
{
lajn x = q.back();
q.pop_back();
lajn y = q.back();
q.push_back(x);
return y;
}
void calc(int idx,int n)
{
deque <lajn> q;
for(int i = idx; i <= n; i++)
{
while(1)
{
if(q.size()<=1)break;
lajn a=q.front();
q.pop_front();
lajn b=q.front();
if(f(a,s[i])<=f(b,s[i]))continue;
q.push_front(a);
break;
}
if(q.size())
{
dp[idx][i]=f(q.front(),s[i]);
opt[idx][i]=q.front().idx;
}
lajn a;
a.k=s[i];
a.n=-s[i]*s[i]+dp[idx-1][i];
a.idx=i;
while(q.size()>1 && bad(prev_back(q),q.back(),a))q.pop_back();
q.push_back(a);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,k;
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
cin >> s[i];
s[i]+=s[i-1];
}
for(int i = 1; i <= k; i++)
{
calc(i,n);
}
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... |