oj.uz

Submission #263389

# Submission time Handle Problem Language Result Execution time Memory
263389 2020-08-13T16:27:49 Z DS007 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 1000 ms 11052 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5, M = 1e6;
int a[M], n, d, m;

bool check(int mid) {
    queue<int> q;
    for (int i = 1, p = 0; i <= n; i++) {
        while (p < m && a[p] == i)
            q.push(a[p++]);

        for (int j = 0; j < mid && !q.empty(); j++) {
            if (i - q.front() > d)
                return false;
            q.pop();
        }
    }

    return true;
}

int solveTestCase() {
    cin >> n >> d >> m;
    for (int i = 0; i < m; i++) cin >> a[i];
    sort(a, a + m);

    int l = 1, h = M, ans = M;
    while (l <= h) {
        //cerr << l << " " << h << "\n";
        int mid = (l + h) / 2;
        if (check(mid))
            ans = mid, h = mid - 1;
        else
            l = mid + 1;
    }

    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

Compilation message

jobs.cpp: In function 'long long int solveTestCase()':
jobs.cpp:40:1: warning: no return statement in function returning non-void [-Wreturn-type]
   40 | }
      | ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 2320 KB Time limit exceeded
2 Execution timed out 1095 ms 2376 KB Time limit exceeded
3 Execution timed out 1098 ms 2320 KB Time limit exceeded
4 Execution timed out 1089 ms 2344 KB Time limit exceeded
5 Execution timed out 1098 ms 2320 KB Time limit exceeded
6 Execution timed out 1091 ms 2320 KB Time limit exceeded
7 Execution timed out 1095 ms 2320 KB Time limit exceeded
8 Execution timed out 1087 ms 2312 KB Time limit exceeded
9 Execution timed out 1097 ms 1656 KB Time limit exceeded
10 Execution timed out 1082 ms 1776 KB Time limit exceeded
11 Execution timed out 1092 ms 2040 KB Time limit exceeded
12 Execution timed out 1078 ms 3272 KB Time limit exceeded
13 Execution timed out 1097 ms 4084 KB Time limit exceeded
14 Execution timed out 1087 ms 5896 KB Time limit exceeded
15 Execution timed out 1043 ms 6408 KB Time limit exceeded
16 Execution timed out 1080 ms 8324 KB Time limit exceeded
17 Execution timed out 1094 ms 9444 KB Time limit exceeded
18 Execution timed out 1089 ms 9976 KB Time limit exceeded
19 Execution timed out 1077 ms 11052 KB Time limit exceeded
20 Execution timed out 1087 ms 9336 KB Time limit exceeded