Submission #1088818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088818		quangminh412	Advertisement 2 (JOI23_ho_t2)	C++14	33 / 100	228 ms	34828 KiB

Main

#include <bits/stdc++.h>
using namespace std;

/*
  John Watson
  https://codeforces.com/profile/quangminh98

  Mua Code nhu mua Florentino !!
*/

#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

const int oo = 1e9;
const int maxn = 500009;

bool cmp(pair<int, int> a, pair<int, int> b) { return a.second < b.second; }

pair<int, int> x[maxn];
int n;

signed main()
{
	if (fopen("test.inp", "r"))
	{
		freopen("test.inp", "r", stdin);
		freopen("test.out", "w", stdout);
	}
	faster();
	
	cin >> n;
	bool sub1 = true;
	for (int i = 1; i <= n; i++) 
	{
		cin >> x[i].first >> x[i].second;
		if (i != 1 && x[i].second != x[i - 1].second)
			sub1 = false;
	}
	
	if (sub1 == true)
	{
		set<int> se;
		for (int i = 1; i <= n; i++) se.insert(x[i].first);
		cout << se.size() << '\n';
		return 0;
	}
	
	if (n <= 16)
	{
		sort(x + 1, x + n + 1, cmp);
	
		int ans = oo;
		for (int mask = 0; mask < (1 << n); mask++)
		{
			vector<int> process;
			int sz = 0;
			for (int i = 0; i < n; i++)
				if (mask >> i & 1)
					process.push_back(i + 1), sz++;
			vector<int> cnt(n + 4, 0);
			for (int pos : process)
			{
				cnt[pos] = 1;
				for (int p = pos - 1; p > 0; p--)
					if (abs(x[p].first - x[pos].first) <= x[pos].second - x[p].second)
						cnt[p] = 1;
			}
			bool mark = true;
			for (int i = 1; i <= n; i++)
				if (cnt[i] == 0)
					mark = false;
			if (mark == true)
				ans = min(ans, sz);
		}
	
		cout << ans << '\n';	
		return 0;	
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   freopen("test.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   freopen("test.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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