Submission #263411

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
263411	2020-08-13T16:44:23 Z	DS007	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	76 ms	1400 KB

jobs

#include <bits/stdc++.h>
using namespace std;

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

bool check(int mid) {
    for (int i = 1; i <= n; i++)
        cpy[i] = a[i];

    for (int i = 1, last = 1; i <= n; i++) {
        int left = mid;
        while (left && last <= i) {
            if (left >= cpy[last])
                left -= cpy[last++];
            else
                cpy[last] -= left, left = 0;
        }

        if (last > n + 1)
            exit(0);
        if (i - last > d)
            return false;
    }

    return true;
}

int solveTestCase() {
    cin >> n >> d >> m;
    for (int i = 0; i < m; i++) {
        int temp;
        cin >> temp;
        if (temp >= N)
            exit(0);
        a[temp]++;
    }

    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 'int solveTestCase()':
jobs.cpp:49:13: warning: control reaches end of non-void function [-Wreturn-type]
   49 |     cout << ans;
      |             ^~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	9 ms	640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	8 ms	640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	9 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	10 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	9 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	8 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	9 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	9 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	13 ms	1280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	19 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	11 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	16 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	24 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	36 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	44 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	50 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	62 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	62 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	76 ms	1400 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	61 ms	632 KB	Execution killed with signal 11 (could be triggered by violating memory limits)