oj.uz

Submission #84453

# Submission time Handle Problem Language Result Execution time Memory
84453 2018-11-15T08:24:13 Z someone_aa Job Scheduling (CEOI12_jobs) C++17
0 / 100
 1000 ms 33792 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
multiset<int>tasks;
int n, d, m;

bool check(int x) {
    multiset<int> curr = tasks;
    for(int i=1;i<=n;i++) {
        //cout<<i<<": \n";
        for(int j=0;j<x && curr.size();j++) {
            auto it = curr.lower_bound(i-d);
            //cout<<"Found: "<<(*it)<<"\n";
            if(curr.size() == 0 && it == curr.end()) break;
            if(*it > i) break;
            else curr.erase(it);
        }
    }
    return curr.size() == 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>d>>m;
    int x;
    for(int i=1;i<=m;i++) {
        cin>>x;
        tasks.insert(x);
    }

    int index = m;
    for(int cekor = m/2;cekor>0;cekor/=2) {
        while(index-cekor>=0 && check(index-cekor)) index-=cekor;
    }
    cout<<index<<"\n";

    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 19704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 106 ms 19968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 102 ms 19968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 103 ms 19992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 101 ms 20140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 105 ms 20384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 104 ms 20384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 107 ms 20416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 132 ms 20416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 139 ms 20416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 278 ms 20416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Execution timed out 1085 ms 29504 KB Time limit exceeded
13 Execution timed out 1076 ms 33792 KB Time limit exceeded
14 Runtime error 419 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 428 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 633 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 761 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 584 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 562 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 829 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)