Submission #941244

#	Time	Username	Problem	Language	Result	Execution time	Memory
941244		dsyz	Advertisement 2 (JOI23_ho_t2)	C++17	33 / 100	250 ms	38704 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	pair<ll,ll> arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i].first>>arr[i].second;
	}
	if(N > 1000){
		set<ll> s;
		for(ll i = 0;i < N;i++){
			s.insert(arr[i].first);
		}
		cout<<s.size()<<'\n';
	}else{
		ll mini = 1e18;
		for(ll bitmask = 0;bitmask < (1ll<<N);bitmask++){
			ll sum = 0;
			bool done[N];
			memset(done,0,sizeof(done));
			for(ll i = 0;i < N;i++){
				if(bitmask & (1ll<<i)){
					done[i] = 1;
					for(ll j = 0;j < N;j++){
						if(abs(arr[i].first - arr[j].first) <= arr[i].second - arr[j].second){
							done[j] = 1;
						}
					}
					sum++;
				}
			}
			bool ok = 1;
			for(ll i = 0;i < N;i++){
				if(!done[i]){
					ok = 0;
				}
			}
			if(ok){
				mini = min(mini,sum);
			}
		}
		cout<<mini<<'\n';
	}
}

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