#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 = n;
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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
1924 KB |
Output isn't correct |
| 2 |
Incorrect |
127 ms |
2000 KB |
Output isn't correct |
| 3 |
Incorrect |
129 ms |
2000 KB |
Output isn't correct |
| 4 |
Incorrect |
139 ms |
2004 KB |
Output isn't correct |
| 5 |
Incorrect |
124 ms |
2008 KB |
Output isn't correct |
| 6 |
Incorrect |
137 ms |
2000 KB |
Output isn't correct |
| 7 |
Incorrect |
137 ms |
2020 KB |
Output isn't correct |
| 8 |
Incorrect |
129 ms |
1924 KB |
Output isn't correct |
| 9 |
Incorrect |
229 ms |
2032 KB |
Output isn't correct |
| 10 |
Incorrect |
245 ms |
2000 KB |
Output isn't correct |
| 11 |
Incorrect |
111 ms |
2020 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
278 ms |
3468 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
391 ms |
5360 KB |
Unexpected end of file - int32 expected |
| 14 |
Execution timed out |
1051 ms |
7104 KB |
Time limit exceeded |
| 15 |
Incorrect |
888 ms |
8784 KB |
Output isn't correct |
| 16 |
Execution timed out |
1071 ms |
10356 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1049 ms |
11816 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1074 ms |
13416 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1076 ms |
14948 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1076 ms |
11984 KB |
Time limit exceeded |
