Submission #1144774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144774		Nomio	Advertisement 2 (JOI23_ho_t2)	C++20	69 / 100	2061 ms	492764 KiB

Main

#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;
		for(int i = 0; i < n; i++) {
			s.insert({x[i], e[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';
	} else {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(abs(x[i] - x[j]) <= e[i] - e[j]) {
					chi[i].insert(j);
					par[j].insert(i);
				}
			}
		}
		set<int> S;
		int ans = 0;
		while(S.size() != n) {
			int id = -1, mx = 0;
			for(int i = 0; i < n; i++) {
				if((int)chi[i].size() > mx) {
					mx = (int)chi[i].size();
					id = i;
				}
			}
			if(id != -1) {
				S.insert(id);
				vector<int> vec;
				for(int x : chi[id]) {
					S.insert(x);
					vec.push_back(x);
				}
				for(int x : vec) {
					for(int y : par[x]) {
						chi[y].erase(x);
					}
				}
				chi[id].clear();
			}
			ans++;
		}
		cout << ans << '\n';
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 0 / 31