oj.uz

Submission #263409

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

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;
        }

        assert(last <= n + 1);
        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 'long long 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 652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 9 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 9 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 8 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 9 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 8 ms 744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 8 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 14 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 13 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 8 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 15 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 24 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 36 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 39 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 56 ms 856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 59 ms 844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 58 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 83 ms 2192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 62 ms 852 KB Execution killed with signal 11 (could be triggered by violating memory limits)