Submission #1019679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019679		crispxx	Advertisement 2 (JOI23_ho_t2)	C++14	33 / 100	312 ms	38612 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
		
#define int ll
#define nl '\n'
#define vt vector
#define ar array
#define ff first
#define ss second
#define all(x) x.begin(), x.end()

#define px cout << "YES\n"
#define py cout << "NO\n"

void _() {
	int n; cin >> n;
	vt<int> x(n), e(n);
	for(int i = 0; i < n; i++) {
		cin >> x[i] >> e[i];
	}
	// e1 = e2 = · · · = eN
	set<int> s(e.begin(), e.end());
	if(s.size() == 1) {
		set<int> t(x.begin(), x.end());
		cout << (int)t.size() << nl;
		return;
	}
	// otherwise
	int ans = n;
	for(int msk = 0; msk < (1 << n); msk++) {
		int ok = 0;
		for(int i = 0; i < n; i++) {
			if(((msk >> i) & 1) == 0) continue;
			for(int j = 0; j < n; j++) {
				if((msk >> j) & 1 || abs(x[i] - x[j]) <= e[i] - e[j]) {
					ok |= (1 << j);
				}
			}
		}
		if(ok == (1 << n) - 1) {
			int v = __builtin_popcountll(msk);
			ans = min(ans, v);
		}
	}
	cout << ans << nl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt = 1;
	// cin >> tt;
	while(tt--){_();}
}

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