Submission #743132

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743132	2023-05-17T08:16:33 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1000 ms	14440 KB

jobs

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+1;
int n,d,m;

struct job
{
    int dline,idx;

    bool operator <(const job &x)const{
        if(dline != x.dline) return dline > x.dline;
        return idx > x.idx;
    }
};

int ans;
vector<int> path;
priority_queue<job> pq;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> d >> m;
    for(int i=1;i<=m;++i)
    {
        int x;
        cin >> x;
        x += d;
        pq.push({x,i});
    }
//    while(!pq.empty())
//    {
//        cout << pq.top().dline << " " << pq.top().idx << '\n';
//        pq.pop();
//    }
    int l = 1,r = 1e9+7;
    while(l<=r)
    {
        priority_queue<job> tmp = pq;
        int mid = (l+r)/2;
//        cout << "mid = " << mid << '\n';
        bool all = true;
        bool cant = false;
        int cnt=0;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=mid;++j)
            {
//                cout << "day = " << i << " deadline now " << tmp.top().dline << '\n';
                if(i > tmp.top().dline)
                {
                    cant = true;
                    break;
                }
                if(!tmp.empty()) tmp.pop();
            }
            if(cant) break;
        }
        if((!cant) && tmp.empty())
        {
            r = mid-1;
            ans = mid;
        }
        else l = mid+1;
//        cout << "\n\n";
    }
    cout << ans << '\n';
//    int d = 0;
//    while(!pq.empty())
//    {
//        for(int i=1;i<=ans;++i)
//        {
//            cout << pq.top().idx << " ";
//            pq.pop();
//        }
//        ++d;
//        cout << "0\n";
//    }
//    while(d < n)
//    {
//        cout << "0\n";
//        d++;
//    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:42:14: warning: unused variable 'all' [-Wunused-variable]
   42 |         bool all = true;
      |              ^~~
jobs.cpp:44:13: warning: unused variable 'cnt' [-Wunused-variable]
   44 |         int cnt=0;
      |             ^~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1068 ms	2256 KB	Time limit exceeded
2	Execution timed out	1079 ms	2256 KB	Time limit exceeded
3	Execution timed out	1079 ms	2256 KB	Time limit exceeded
4	Execution timed out	1074 ms	2256 KB	Time limit exceeded
5	Execution timed out	1079 ms	2256 KB	Time limit exceeded
6	Execution timed out	1085 ms	2256 KB	Time limit exceeded
7	Execution timed out	1078 ms	2256 KB	Time limit exceeded
8	Execution timed out	1068 ms	2256 KB	Time limit exceeded
9	Execution timed out	1083 ms	2256 KB	Time limit exceeded
10	Execution timed out	1079 ms	2256 KB	Time limit exceeded
11	Execution timed out	1076 ms	2256 KB	Time limit exceeded
12	Execution timed out	1053 ms	3780 KB	Time limit exceeded
13	Execution timed out	1053 ms	5464 KB	Time limit exceeded
14	Execution timed out	1071 ms	7068 KB	Time limit exceeded
15	Execution timed out	1066 ms	8272 KB	Time limit exceeded
16	Execution timed out	1062 ms	9836 KB	Time limit exceeded
17	Execution timed out	1053 ms	11464 KB	Time limit exceeded
18	Execution timed out	1070 ms	12936 KB	Time limit exceeded
19	Execution timed out	1058 ms	14440 KB	Time limit exceeded
20	Execution timed out	1038 ms	11360 KB	Time limit exceeded