Submission #1234137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234137		just	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	157 ms	9144 KiB

jobs

#include "bits/stdc++.h"
using namespace std;
 
#define vec vector
#define int long long
#define all(x) (x).begin(), (x).end()
 
const int mod = 1e9 + 7;
const int inf = 1e18;

template<typename T>
void print(const vec<T> &v) {
    for (auto &x: v) cerr << x << " ";
    cerr << endl;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, d, m; cin >> n >> d >> m;
	vec<int> day(m), cnt(n, 0);
	for(int &x: day) cin >> x, x--, cnt[x]++;
	
	print(cnt);
	
	auto can = [&](int x) {
	    vec<int> tmp = cnt;
	    int i = 0, j = 0;
		while (j < n) {
		    int q = x;
			while (true) {
			    if (tmp[i] != 0) {
					int rem = min(q, tmp[i]);
					q -= rem;
					tmp[i] -= rem;	
				}
				
				if (tmp[i] == 0 && i < j) i++;
				else break;
			}
			
			int gap;
			if (tmp[i] == 0) gap = 0;
			else gap = j - i + 1;
			if (gap > d) return false;
			
			j++;
		}
		
		return true;
	};
	
	int l = 0, r = m, ans = m;
	while (l <= r) {
	    int mid = l + (r - l) / 2;
		if (can(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	
	cout << ans << "\n";
}

• Subtask 1: 0 / 100