Submission #1144709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144709		Nomio	Advertisement 2 (JOI23_ho_t2)	C++20	33 / 100	555 ms	99992 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;
		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;
}

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