Submission #1226457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226457		chaeryeong	Arcade (NOI20_arcade)	C++20	0 / 100	0 ms	320 KiB

Arcade

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
t[j] - t[i] >= abs(a[i] - a[j])
t[j] - t[i] >= a[i] - a[j] and t[j] - t[i] >= a[j] - a[i]


t[j] + a[j] >= t[i] + a[i] and t[j] - a[j] >= t[i] - a[i]
*/
const int M = 5e5 + 25;
int n, m;
array <ll, 2> a[M];
int vis[M];
void solve () {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a[i][0];
	}
	for (int i = 1; i <= m; i++) {
		cin >> a[i][1];
	}
	sort(a + 1, a + m + 1);
	for (int i = 1; i <= m; i++) {
		a[i] = {a[i][0] - a[i][1], a[i][0] + a[i][1]};
	}
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		cnt += !vis[i];
		vis[i] = 1;
		int pos = 0;
		for (int j = i + 1; j <= m; j++) {
			if (!vis[j] && a[j][0] >= a[i][0] && a[j][1] >= a[i][1]) {
				if (pos == 0 || a[j][0] < a[pos][0] || (a[j][0] == a[pos][0] && a[j][1] < a[pos][1])) {
					pos = j;
				}
			}
		}
		vis[pos] = 1;
	}
	cout << cnt << '\n';
}	
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 14
• Subtask 6: 0 / 20
• Subtask 7: 0 / 15