Submission #670420

#	Time	Username	Problem	Language	Result	Execution time	Memory
670420		asdf334	Job Scheduling (CEOI12_jobs)	C++17	20 / 100	244 ms	18652 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)x.size()
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int N, D, M; cin >> N >> D >> M;
	map<int, vector<int>> vals;
	for (int i = 1; i <= M; ++i) {
		int num; cin >> num;
		vals[num].push_back(i);
	}
	int left = 1; int right = 1e6;
	while (left < right) {
		int mid = left + (right - left) / 2;
		ll curr = 0; int del = 0;
		for (auto val : vals) {
			curr = max(curr, (ll)mid * (val.first - 1)); curr += sz(val.second);
			del = max(del, (int)ceil(curr / mid) - val.first);
		} 
		if (del > D) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	cout << left << '\n';
	int ctr = 0; vector<vector<int>> ans(N);
	for (auto val : vals) {
		for (int num : val.second) {
			if (sz(ans[ctr]) >= left) ++ctr;
			ans[ctr].push_back(num);
		}
	}
	for (vector<int> day : ans) {
		for (int req : day) {
			cout << req << " ";
		}
		cout << 0 << '\n';
	}
}

• Subtask 1: 20 / 100