Submission #93992

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
93992	2019-01-14T11:26:38 Z	rkocharyan	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	71 ms	888 KB

jobs

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

int n, d, m;
int f[N];

bool check(int t) {
    deque < pair <int, int> > h;
    for(int i = 1; i <= n; i++) {
        h.emplace_back(i, f[i]);
        if(!h.empty()) {
            h[0].second -= min(h[0].second, t);
            int cur_t = t;
            if(!h.empty() && cur_t) {
                if(i - h[0].first > d) return false;
                int next_t = cur_t;
                next_t -= min(h[0].second, cur_t);
                h[0].second -= min(h[0].second, cur_t);
                cur_t = next_t;
                if(h[0].second == 0) {
                    h.pop_back();
                }
            }
        }
    }
    if(h.size()) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d >> m;
    for(int i = 0; i < m; i++) {
        int x;
        cin >> x;
        f[x]++;
    }
    int low = 1, high = n, best = n;
    while(low <= high) {
        int mid = (low + high) >> 1;
        if(check(mid)) {
            best = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << best << '\n';
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	8 ms	632 KB	Output isn't correct
2	Incorrect	8 ms	632 KB	Output isn't correct
3	Incorrect	8 ms	632 KB	Output isn't correct
4	Incorrect	8 ms	632 KB	Output isn't correct
5	Incorrect	8 ms	632 KB	Output isn't correct
6	Incorrect	8 ms	632 KB	Output isn't correct
7	Incorrect	8 ms	632 KB	Output isn't correct
8	Incorrect	8 ms	632 KB	Output isn't correct
9	Incorrect	14 ms	628 KB	Output isn't correct
10	Incorrect	14 ms	504 KB	Output isn't correct
11	Incorrect	9 ms	632 KB	Output isn't correct
12	Incorrect	15 ms	632 KB	Output isn't correct
13	Incorrect	22 ms	632 KB	Output isn't correct
14	Incorrect	33 ms	760 KB	Output isn't correct
15	Incorrect	36 ms	716 KB	Output isn't correct
16	Incorrect	47 ms	760 KB	Output isn't correct
17	Incorrect	53 ms	740 KB	Output isn't correct
18	Incorrect	55 ms	624 KB	Output isn't correct
19	Incorrect	71 ms	716 KB	Output isn't correct
20	Incorrect	54 ms	888 KB	Output isn't correct