#include<cstdio>
#include<algorithm>
std::pair<std::pair<long long,long long>,int> s[100000];
int sn;
long long a[100001];
long long d[2][100001];
int vi[201][100001];
void insert(long long a,long long b,int c)
{
double t;
while(sn>=2)
{
if((s[sn-1].first.second-s[sn-2].first.second)*(b-s[sn-2].first.second)>(s[sn-1].first.first-s[sn-2].first.first)*(a-s[sn-2].first.first))break;
sn--;
}
s[sn++]=std::make_pair(std::make_pair(a,b),c);
}
void print(int i,int j)
{
if(i)
{
print(i-1,vi[i][j]);
printf("%d ",vi[i][j]);
}
}
int main()
{
int i,j,k,n,m;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
a[i]+=a[i-1];
d[0][i]=a[i]*a[i];
}
for(i=1;i<=m;i++)
{
k=0;
sn=0;
for(j=1;j<=n;j++)
{
insert(-2*a[j-1],a[j-1]*a[j-1]+d[!(i&1)][j-1],j-1);
if(k>=sn)k=sn-1;
while(k+1<sn)
{
if(-(s[k+1].first.second-s[k].first.second)<a[j]*(s[k+1].first.first-s[k].first.first))break;
k++;
}
d[i&1][j]=a[j]*a[j]+s[k].first.first*a[j]+s[k].first.second;
vi[i][j]=s[k].second;
}
}
printf("%lld\n",(a[n]*a[n]-d[m&1][n])/2);
print(m,n);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
84292 KB |
Output isn't correct - contestant didn't find the optimal answer: 106 < 108 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
