Submission #706801

#	Time	Username	Problem	Language	Result	Execution time	Memory
706801		TAhmed33	Job Scheduling (CEOI12_jobs)	C++98	0 / 100	349 ms	24056 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, d, m;
pair <int, int> arr[1000001] = {};
int bs (int pos, int x) {
	int l = 1, r = m;
	int mid, ans = m + 1;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (arr[mid].first > x) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	return ans;
}
bool check (int x) {
	int cnt = 1;
	int i = 1;
	int a;
	while ((a = min((int)i + x, (int)bs(i + 1, arr[i].first + d))) != m + 1) {
		cnt++;
		i = a;
	}
	return (cnt <= n);
}
signed main () {
	cin >> n >> d >> m;
	map <int, vector <int>> positions;
	for (int i = 1; i <= m; i++) {
		cin >> arr[i].first;
		arr[i].second = i;
		positions[arr[i].first].push_back(i);
	}
	sort(arr + 1, arr + m + 1);
	int l = 1, r = n;
	int mid, ans;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) {
			r = mid - 1;
			ans = mid;
		} else l = mid + 1;
	}
	cout << ans << endl;
}		

• Subtask 1: 0 / 100