Submission #1125743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125743		abel2008	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	1099 ms	84916 KiB

jobs

#include <iostream>
#include <set>
using namespace std;
int n,d,m,val;
multiset<int> requests;

bool solve(int crtd) {
        multiset<int> req = requests,todo;
        for (int i = 1;i<=n;++i) {
                while(!req.empty()&&*req.begin()<=i) {
                        todo.insert(*req.begin());
                        req.erase(req.find(*req.begin()));
                }
                for (int j = 1;j<=crtd;++j) {
                        if (!todo.empty()) {
                                int num = *todo.begin();
                                todo.erase(todo.find(*todo.begin()));
                                if (num+d<i) {
                                        return 0;
                                }
                        }
                }
        }
        if (!todo.empty())
                return 0;
        return 1;
}

int main() {
        cin>>n>>d>>m;
        for (int i = 1;i<=m;++i) {
                cin>>val;
                requests.insert(val);
        }
        int st = 1,dr = n;
        while(st<dr) {
                int mid = (st+dr)/2;
                if (solve(mid)) {
                        dr = mid;
                } else {
                        st = mid+1;
                }
        }
        cout<<dr;
        return 0;
}

• Subtask 1: 0 / 100