#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
mt19937 rnd(1823764);
int n,k;
int a[1000005];
int inita[1000005];
int root[1000005];
int tole[1000005];
int tori[1000005];
priority_queue<pair<int,int>> pq;
void afis()
{
/*for(int i=1;i<=n;i++)
cout<<a[root[i]]<<" ";
cout<<"\n";*/
/*for(int i=1;i<=n;i++)
{
if(i==1 || root[i]!=root[i-1])
{
cout<<root[i]<<" "<<tole[root[i]]<<" "<<tori[root[i]]<<" "<<a[root[i]]<<"\n";
}
}*/
}
void initializeaza_secvente()
{
if(a[1]==a[n])
{
for(int i=1;i<=n;i++)
{
if(a[i]!=a[1])
break;
root[i]=1;
tori[1]=i;
}
for(int i=n;i>0;i--)
{
if(a[i]!=a[n])
break;
root[i]=1;
tole[1]=i;
}
int aux = tori[1]+1;
root[aux] = aux;
tole[aux] = aux;
for(int i=tori[1]+2;i<tole[1];i++)
{
if(a[i]!=a[i-1])
{
tori[aux]=i-1;
aux=i;
tole[i]=i;
}
root[i]=aux;
}
tori[aux]=tole[1]-1;
}
else
{
int aux=1;
root[1]=1;
tole[1]=1;
for(int i=2;i<=n;i++)
{
if(a[i]!=a[i-1])
{
tori[aux]=i-1;
aux=i;
tole[i]=i;
}
root[i]=aux;
}
tori[aux]=n;
}
for(int i=1;i<=n;i++)
{
if(root[i]==i)
{
int tol = tole[i]-1;
if(tol==0)
tol=n;
int tor = tori[i]+1;
if(tor==n+1)
tor=1;
if(a[tol]>a[i] && a[tor]>a[i])
{
pq.push({-(tori[i]-tole[i]),i});
}
}
}
//for(int i=1;i<=n;i++)
// cout<<root[i]<<" ";
}
void unite(int x, int y)
{
if(tori[x]-tole[x] <= tori[y]-tole[y])
{
tole[y] = tole[x];
int j = tole[x];
while(j!=tori[x])
{
root[j] = y;
j++;
if(j==n+1)
j=0;
}
root[tori[x]] = y;
}
else
{
tori[x] = tori[y];
int j = tole[y];
while(j!=tori[y])
{
root[j] = x;
j++;
if(j==n+1)
j=0;
}
root[tori[y]] = x;
}
}
void verif_debug()
{
}
int dp[105][1005][1005];///dp[i][cnt][ult]
int solve_dp()
{
int mnm=INF;
for(int primu=0;primu<=k;primu++)
{
for(int i=0;i<=k;i++)
for(int j=0;j<=k;j++)
dp[1][i][j]=INF;
dp[1][primu][primu] = 0;
for(int i=2;i<=n;i++)
{
for(int cnt=0;cnt<=k;cnt++)
{
for(int u=0;u<=cnt;u++)
{
dp[i][cnt][u] = INF;
for(int p=0;p+u<=cnt;p++)
{
dp[i][cnt][u] = min(dp[i][cnt][u], dp[i-1][cnt-u][p] + abs((a[i]+u) - (a[i-1]+p)));
}
//if(dp[i][cnt][u]<INF) cout<<i<<" "<<cnt<<" "<<u<<" "<<dp[i][cnt][u]<<"\n";
}
}
}
for(int cnt=0;cnt<=k;cnt++)
{
for(int u=0;u<=cnt;u++)
{
mnm = min(mnm, dp[n][cnt][u] + abs((a[n]+u) - (a[1]+primu)));
}
}
}
mnm = -mnm;
for(int i=1;i<n;i++)
mnm += abs(a[i]-a[i+1]);
mnm += abs(a[1]-a[n]);
return mnm;
}
signed main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
cout<<solve_dp();
return 0;
while(1)
{
for(int i=1;i<=n;i++)
{
inita[i] = rnd()%1000000000;
a[i] = inita[i];
}
bool bl=1;
int sum=0;
for(int i=1;i<=n;i++)
{
if(a[i]!=a[1])
bl=0;
if(i>1) sum += abs(a[i]-a[i-1]);
}
int rezdp = solve_dp();
sum += abs(a[1]-a[n]);
if(bl)
{
cout<<0;
return 0;
}
initializeaza_secvente();
while(!pq.empty())
{
verif_debug();
int x = pq.top().second;
pq.pop();
cout<<x<<" zzz\n";
if(tori[x]-tole[x]+1 > k)
break;
int tol = tole[x]-1;
if(tol==0)
tol=n;
int tor = tori[x]+1;
if(tor==n+1)
tor=1;
if((tori[x]-tole[x]+1) * (min(a[root[tol]],a[root[tor]]) - a[x]) < k)
{
if(a[root[tol]]<a[root[tor]])
{
k -= (tori[x]-tole[x]+1) * (a[root[tol]] - a[x]);
a[x] = a[root[tol]];
unite(root[tol], x);
}
else if(a[root[tol]]>a[root[tor]])
{
k -= (tori[x]-tole[x]+1) * (a[root[tor]] - a[x]);
a[x] = a[root[tor]];
unite(x, root[tor]);
}
else
{
k -= (tori[x]-tole[x]+1) * (a[root[tor]] - a[x]);
a[x] = a[root[tor]];
unite(root[tol], x);
unite(root[x], root[tor]);
}
}
else
{
a[x] += k / (tori[x]-tole[x]+1);
afis();
break;
}
afis();
bool eq=1;
for(int i=1;i<=n;i++)
{
if(root[i]!=root[1])
{
eq=0;
break;
}
}
if(eq)
{
//cout<<"oh no equal\n";
break;
}
///trebuie sa verificam daca tot sirul ii egal, atunci dam break
x = root[x];
tol = tole[x]-1;
if(tol==0)
tol=n;
tor = tori[x]+1;
if(tor==n+1)
tor=1;
if(a[tol] > a[x] && a[tor] > a[x])
{
pq.push({-(tori[x]-tole[x]),x});
}
}
for(int i=1;i<n;i++)
{
sum -= abs(a[root[i+1]] - a[root[i]]);
}
sum -= abs(a[root[n]] - a[root[1]]);
//cout<<sum;
if(sum!=rezdp)
{
///do something
for(int i=1;i<=n;i++)
{
cout<<inita[i]<<" ";
}
return 0;
}
}
return 0;
}
/**
9 1000
1 1 1 2 2 3 3 1 1
9 1000
1 1 1 3 3 3 3 1 1
10 1000
5 4 3 2 1 1 2 3 4 5
8 3
7 9 1 1 9 9 9 9
n = 2 ?????
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2049 ms |
62176 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
