#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];
int lun(int x)
{
if(tole[x]<=tori[x])
return tori[x]-tole[x]+1;
else
return (n-tole[x]+1) + tori[x];
}
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({-lun(i),i});
}
}
}
//for(int i=1;i<=n;i++)
// cout<<root[i]<<" ";
}
void unite(int x, int y)
{
if(lun(x) <= lun(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;
}
int solve_greedy()
{
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]);
}
sum += abs(a[1]-a[n]);
if(bl)
{
return 0;
//cout<<0;
//return 0;
}
initializeaza_secvente();
while(!pq.empty())
{
verif_debug();
int x = pq.top().second;
pq.pop();
//cout<<x<<" zzz\n";
if(lun(x) > k)
break;
int tol = tole[x]-1;
if(tol==0)
tol=n;
int tor = tori[x]+1;
if(tor==n+1)
tor=1;
if(lun(x) * (min(a[root[tol]],a[root[tor]]) - a[x]) < k)
{
if(a[root[tol]]<a[root[tor]])
{
k -= lun(x) * (a[root[tol]] - a[x]);
a[x] = a[root[tol]];
unite(root[tol], x);
}
else if(a[root[tol]]>a[root[tor]])
{
k -= lun(x) * (a[root[tor]] - a[x]);
a[x] = a[root[tor]];
unite(x, root[tor]);
}
else
{
k -= lun(x) * (a[root[tor]] - a[x]);
a[x] = a[root[tor]];
unite(root[tol], x);
unite(root[x], root[tor]);
}
}
else
{
a[x] += k / lun(x);
afis();
break;
}
afis();
bool eq=1;
for(int i=1;i<=n;i++)
{
if(root[i]!=root[1])
{
eq=0;
break;
}
}
if(eq)
{
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({-lun(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]]);
return sum;
}
signed main()
{
int initk;
cin>>n>>initk;
k=initk;
for(int i=1;i<=n;i++)cin>>a[i];
//cout<<solve_dp();
cout<<solve_greedy();
return 0;
while(1)
{
for(int i=1;i<=n;i++)
{
inita[i] = rnd()%10;
a[i] = inita[i];
}
k = initk;
int rezdpp = solve_dp();
int rezgreedy = solve_greedy();
//cout<<sum;
if(rezgreedy!=rezdpp)
{
//cout<<rezdpp<<" "<<rezgreedy<<"\n";
///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 ?????
3 3
4 8 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 10 |
Correct |
29 ms |
11444 KB |
Output is correct |
| 11 |
Correct |
34 ms |
12788 KB |
Output is correct |
| 12 |
Correct |
34 ms |
11420 KB |
Output is correct |
| 13 |
Correct |
271 ms |
43824 KB |
Output is correct |
| 14 |
Correct |
280 ms |
43860 KB |
Output is correct |
| 15 |
Correct |
287 ms |
41768 KB |
Output is correct |
| 16 |
Correct |
275 ms |
42944 KB |
Output is correct |
| 17 |
Correct |
251 ms |
42916 KB |
Output is correct |
| 18 |
Correct |
268 ms |
43600 KB |
Output is correct |
| 19 |
Correct |
277 ms |
43888 KB |
Output is correct |
| 20 |
Correct |
514 ms |
35920 KB |
Output is correct |
