Submission #691046

#	Time	Username	Problem	Language	Result	Execution time	Memory
691046		mohammedMonem	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	830 ms	65536 KiB

jobs

#include<bits/stdc++.h>
[[maybe_unused]] typedef long long ll;
[[maybe_unused]] const int N = (int) 1e6 + 20;
[[maybe_unused]] const int mod = (int) 1e9 + 7;
[[maybe_unused]] char endl = '\n';
[[maybe_unused]] char space = ' ';
[[maybe_unused]] const int off = 1 << 18;
void Run();

int main()
{
    Run();

    //in
    int t = 1;
//    std::cin >> t;
    while (t--) {
        int n,d,m;
        std::cin >> n >> d >> m;
        std::set<std::pair<int,int>,std::greater<>> s;
        for (int i = 1; i <= m; ++i) {
            int x;
            std::cin >> x;
            s.insert({x,i});
        }

        //ops
        std::vector<std::queue<int>> days(n + 1);
        std::vector<int> rm(m,n + 1);//pos of rightmost day wth i as num of jobs
        for (const auto &[u,v]: s) {
            int low = int(std::lower_bound(rm.begin(), rm.end(),u) - rm.begin());
            rm[low] = std::min(rm[low], u + d);
            days[rm[low]--].push(v);
            if (rm[low + 1] == n + 1) {
                rm[low + 1] = rm[low] + 1;
            }
        }

        //out
        int max = INT_MIN;
        for (const auto &item: days) {
            max = std::max((int)item.size(),max);
        }
        std::cout << max << endl;
//        for (int i = 1; i <= n; ++i) {
//            while(!days[i].empty()) {
//                std::cout << days[i].front() << space;
//                days[i].pop();
//            }
//            std::cout << 0 << endl;
//        }
    }

    return 0;
}
void Run(){
    std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
#endif
}

• Subtask 1: 0 / 100