oj.uz

Submission #263420

# Submission time Handle Problem Language Result Execution time Memory
263420 2020-08-13T16:50:16 Z DS007 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 88 ms 1280 KB 
#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 > 0 && last <= i) {
            if (left >= cpy[last])
                left -= cpy[last], 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 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 8 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 8 ms 640 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 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 8 ms 524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 14 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 14 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 10 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 19 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 42 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 38 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 52 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 88 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 73 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 78 ms 1272 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)