oj.uz

Submission #987418

# Submission time Handle Problem Language Result Execution time Memory
987418 2024-05-22T18:02:25 Z OAleksa Job Scheduling (CEOI12_jobs) C++14
0 / 100
 1000 ms 49208 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 1e6 + 69;
int n, d, m;
pair<int, int> a[N];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> d >> m;
  	for (int i = 1;i <= m;i++) {
  		cin >> a[i].f;
  		a[i].s = i;
  	}
  	sort(a + 1, a + m + 1);
  	int l = 1, r = m, ans = 0;
  	auto check = [&](int mid) {
  		int t = 0, s = 1;
  		for (int i = 1;i <= m;i++) {
  			t += 1;
  			if (t > mid) {
  				s += 1;
  				t = 1;
  			}	
  			if (s < a[i].f) {
  				s = a[i].f;
  				t = 1;
  			}
  			if (a[i].f + d < s)
  				return false;
  		}
  		return true;
  	};
  	while (l <= r) {
  		int mid = (l + r) / 2;
  		if (check(mid)) {
  			ans = mid;
  			r = mid - 1;
  		}
  		else 
  			l = mid + 1;
  	}
  	cout << ans << '\n';
  	for (int i = 1;i <= n;i++) {
  		if (i > n - d) {
  			cout << 0 << '\n';
  			continue;
  		}
  		for (int j = 1;j <= ans + 1;j++)
  			cout << 0 << ' ';
  		cout << '\n';
  	}
  }
  return 0; 
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1029 ms 46868 KB Time limit exceeded
2 Execution timed out 1052 ms 44080 KB Time limit exceeded
3 Execution timed out 1035 ms 44356 KB Time limit exceeded
4 Execution timed out 1056 ms 45056 KB Time limit exceeded
5 Execution timed out 1048 ms 48256 KB Time limit exceeded
6 Execution timed out 1052 ms 44672 KB Time limit exceeded
7 Execution timed out 1035 ms 43600 KB Time limit exceeded
8 Execution timed out 1057 ms 45496 KB Time limit exceeded
9 Execution timed out 1058 ms 45008 KB Time limit exceeded
10 Execution timed out 1022 ms 45956 KB Time limit exceeded
11 Incorrect 20 ms 1244 KB Expected EOLN
12 Incorrect 40 ms 2144 KB Expected EOLN
13 Incorrect 62 ms 3156 KB Expected EOLN
14 Incorrect 86 ms 4180 KB Expected EOLN
15 Incorrect 103 ms 5200 KB Expected EOLN
16 Incorrect 132 ms 6484 KB Expected EOLN
17 Incorrect 149 ms 7320 KB Expected EOLN
18 Incorrect 508 ms 22612 KB Expected EOLN
19 Execution timed out 1076 ms 49208 KB Time limit exceeded
20 Incorrect 151 ms 7248 KB Expected EOLN