oj.uz

Submission #263401

# Submission time Handle Problem Language Result Execution time Memory
263401 2020-08-13T16:34:36 Z DS007 Job Scheduling (CEOI12_jobs) C++14
0 / 100
 74 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;
        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:1: warning: no return statement in function returning non-void [-Wreturn-type]
   46 | }
      | ^

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 10 ms 768 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 10 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 17 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 10 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 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 35 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 49 ms 760 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 69 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 74 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)