oj.uz

Submission #263405

# Submission time Handle Problem Language Result Execution time Memory
263405 2020-08-13T16:40:37 Z DS007 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 70 ms 2048 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) {
    copy(a, a + n + 1, cpy);

    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 (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:47:13: warning: control reaches end of non-void function [-Wreturn-type]
   47 |     cout << ans;
      |             ^~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 672 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 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 8 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 8 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 8 ms 640 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 13 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 12 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 16 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 23 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 34 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 37 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 52 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 58 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 62 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 70 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 66 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)