Submission #1144709

#TimeUsernameProblemLanguageResultExecution timeMemory
1144709NomioAdvertisement 2 (JOI23_ho_t2)C++20
33 / 100
555 ms99992 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	ll x[n], e[n];
	set<int> chi[n], par[n];
	set<int> ss;
	for(int i = 0; i < n; i++) {
		cin >> x[i] >> e[i];
		ss.insert(e[i]);
	}
	if(ss.size() == 1) {
		set<pair<int, int> > s;
		set<int> S;
		for(int i = 0; i < n; i++) {
			s.insert({x[i], e[i]});
			S.insert(i);
		}
		cout << s.size() << '\n';
	} else if(n <= 16){
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(i == j) continue;
				if(abs(x[i] - x[j]) <= e[i] - e[j]) {
					chi[i].insert(j);
					par[j].insert(i);
				}
			}
		}
		int mn = n;
		for(int i = 0; i < (1 << n); i++) {
			vector<int> vec;
			set<int> s;
			for(int j = 0; j < n; j++) {
				if((i >> j) % 2 == 1) {
					vec.push_back(j);
				}
			}
			for(int x : vec) {
				s.insert(x);
				for(int X : chi[x]) {
					s.insert(X);
				}
			}
			if(s.size() == n) mn = min(mn, (int) vec.size());
		}
		cout << mn << '\n';
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...