Submission #1226456

#TimeUsernameProblemLanguageResultExecution timeMemory
1226456chaeryeongArcade (NOI20_arcade)C++20
0 / 100
0 ms320 KiB
#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 <= n; 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();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...