oj.uz

Submission #263404

# Submission time Handle Problem Language Result Execution time Memory
263404 2020-08-13T16:39:53 Z DS007 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 71 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;
        assert(temp < N);
        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:46:13: warning: control reaches end of non-void function [-Wreturn-type]
   46 |     cout << ans;
      |             ^~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 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 8 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 10 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 11 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 13 ms 2048 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 17 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 23 ms 760 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 36 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 50 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 56 ms 760 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 71 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 57 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)