# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
339885 | fixikmila | 등산 경로 (IZhO12_route) | C++14 | 128 ms | 28524 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
if(b==0)return 1;
if(b%2==0){
ll t=bin_pow(a,b/2);
return t*t%MOD;
}
else return a*bin_pow(a,b-1)%MOD;
}
vector<ll>a,l,r;
int link[1000000],sz[100000];
int get(int x){
if(x==link[x])return x;
return link[x]=get(link[x]);
}
void unite(int x,int y){
x=get(x);
y=get(y);
//if(sz[x]<sz[y])swap(x,y);
if(x==y)return;
link[y]=x;
sz[x]+=sz[y];
r[x]=r[y];
l[y]=l[x];
}
int main()
{
//freopen("b.in","r",stdin);
//freopen("b.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
cin>>n>>k;
a.resize(n);
l.resize(n);
r.resize(n);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++){
if(i==0)l[i]=n-1;
else l[i]=i-1;
if(i==n-1)r[i]=0;
else r[i]=i+1;
sz[i]=1;
link[i]=i;
}
for(int i=0;i<n;i++){
if(a[i]==a[r[i]])unite(i,r[i]);
}
priority_queue<pair<int,int>>q;
for(int i=0;i<n;i++){
if(link[i]==i&&a[i]<min(a[get(l[i])],a[get(r[i])]))q.push({-sz[i],i});
}
while(!q.empty()){
x=q.top().second;
q.pop();
x=get(x);
y=min(a[get(l[x])],a[get(r[x])])-a[x];
if(y*sz[x]<=k){
// cout<<y<<" "<<sz[x]<<" "<<a[x]<<endl;
k-=y*sz[x];
//cout<<k<<endl;
ans+=2*y;
a[x]+=y;
if(a[x]==a[get(l[x])])unite(l[x],x);
if(a[x]==a[get(r[x])])unite(x,r[x]);
x=get(x);
//a[x]+=y;
//cout<<x<<" "<<a[x]<<" "<<sz[x]<<" "<<a[get(l[x])]<<endl;
if(a[x]<min(a[get(l[x])],a[get(r[x])]))q.push({-sz[x],x});
}
else{
ans+=2*(k/sz[x]);
break;
}
}
cout<<ans;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |