| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 840352 | Lib | Closing Time (IOI23_closing) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
long long U[200003];
long long V[200003];
long long W[200003];
int check[200003];
long long pos[200003];
long long cost1[200003];
long long cost2[200003];
long long pfx1[200003];
long long pfx2[200003];
long long maxroll[200003]; //maxroll[i]=a <==> de "tra no" 1 khoang toi da =a, can rollback it nhat i vi tri tu loai 1 xuong loai 0
long long minupd[200003]; //minupt[i]=k <==> voi 1 budget<=i; upgrade duoc toi da k vi tri tu loai 1 len loai 2
vector <vector <pair <int,int> > > adj;
int main(){
vector <pair <int,int> > temp;
int n,x,y;
long long K;
cin>>n;
cin>>x>>y>>K;
for(int i=0;i<n-1;i++){
cin>>U[i]>>V[i]>>W[i];
pos[i+1]=pos[i]+W[i];
}
for(int i=0;i<n;i++){
cost1[i]=min(abs(pos[i]-pos[x]),abs(pos[i]-pos[y]));
cost2[i]=max(abs(pos[i]-pos[x]),abs(pos[i]-pos[y]))-cost1[i];
pfx1[i+1]=pfx1[i]+cost1[i];
}
int initpos;
long long curmax=0;
for(int i=0;i<n;i++){
pfx2[i+1]=pfx2[i]+cost2[i];
}
for(int i=x+1;i<=y-1;i++){
if(cost1[i]>curmax){
curmax=cost1[i];
initpos=i;
}
}
maxroll[1]=curmax;
for(int i=2;i<y-x;i++){
for(int l=0;l<i;l++){
maxroll[i]=max(maxroll[i],pfx1[initpos+l+1]-pfx1[initpos-(i-l-1)]);
}
}
long long curmin=1000000000000000000;
for(int i=0;i<n;i++){
if(cost2[i]<curmin){
curmin=cost2[i];
initpos=i;
}
}
minupd[1]=1000000000000000000;
for(int i=2;i<=n;i++){
minupd[i]=1000000000000000000;
for(int l=max(0,initpos-i+1);l<=initpos&&l+i-1<n;l++){
minupd[i-1]=min(minupd[i-1],pfx2[l+i]-pfx2[l+1]);
}
}
long long tcost,rcost;
int ans;
int tans=0;
for(int i=0;i<=x;i++){
for(int l=y;l<n;l++){
tcost=pfx1[l+1]-pfx1[i];
rcost=abs(tcost-K);
ans=l-i+1;
if(tcost>K){
for(int a=1;a<=y-x;a++){
if(rcost>=maxroll[a]){
ans-=a;
tans=max(tans,ans);
break;
}
}
}else if(tcost<K){
for(int a=n;a>=0;a--){
if(rcost>=minupd[a]){
ans+=a;
tans=max(tans,ans);
break;
}
}
}else{
tans=max(tans,ans);
}
}
}
cout<<tans;
}
/*
13
3 8 20
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
4
0 3 20
0 1 18
1 2 1
2 3 19
*/