제출 #892237

#제출 시각아이디문제언어결과실행 시간메모리
892237LCJLYAdvertisement 2 (JOI23_ho_t2)C++14
59 / 100
2066 ms4840 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;

void solve(){	
	int n;
	cin >> n;
	pii arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x].first >> arr[x].second;
	}
	
	sort(arr,arr+n);
	
	bool done[n];
	memset(done,0,sizeof(done));
	
	int counter=0;
	while(1){
		int maxi=-1;
		int index=-1;
		
		for(int x=0;x<n;x++){
			if(!done[x]){
				if(arr[x].second>maxi){
					maxi=arr[x].second;
					index=x;
				}
			}
		}
		
		if(maxi==-1) break;
		done[index]=true;
		for(int x=0;x<index;x++){
			if(!done[x]&&arr[index].first-arr[index].second<=arr[x].first-arr[x].second){
				done[x]=true;
			}
		}
		
		for(int x=index+1;x<n;x++){
			if(!done[x]&&arr[index].first+arr[index].second>=arr[x].first+arr[x].second) done[x]=true;
		}
		counter++;
	}
	
	cout << counter;
}

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	//freopen("in.txt", "r", stdin);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}	
}



		


		
		
	
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...