Submission #1226451

#TimeUsernameProblemLanguageResultExecution timeMemory
1226451chaeryeongArcade (NOI20_arcade)C++20
0 / 100
0 ms328 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];
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]};
	}
	vector <array <ll, 2>> ee;
	for (int i = 1; i <= m; i++) {
		bool flag = 0;
		//cout << a[i][0] << " " << a[i][1] << '\n';
		int pos = -1;
		int c = 0;
		for (auto j : ee) {
			if (j[0] <= a[i][0] && j[1] <= a[i][1]) {
				if (pos == -1 || j[0] > a[pos][0]) {
					pos = c;
				}
			}
			c++;
		}
		if (pos == -1) {
			ee.push_back(a[i]);
		} else {
			ee[pos] = a[i];
		}
	}
	cout << (int)ee.size() << '\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...