답안 #840352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
840352	2023-08-31T10:09:46 Z	Lib	봉쇄 시간 (IOI23_closing)	C++17	컴파일 오류	0 ms	0 KB

closing

#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
*/

Compilation message

closing.cpp: In function 'int main()':
closing.cpp:30:6: warning: 'initpos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |  int initpos;
      |      ^~~~~~~
/usr/bin/ld: /tmp/cci8m46A.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccDnx4qA.o:closing.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cci8m46A.o: in function `main':
grader.cpp:(.text.startup+0x6a1): undefined reference to `max_score(int, int, int, long long, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status