#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
int n, d, m, x;
int arr[maxn];
bool check(int x) {
deque<pair<int,int> > dq;
for(int i=1;i<=n;i++) {
dq.pb(mp(i, arr[i]));
int value = x;
/*cout<<"Before processing: \n";
for(auto i:dq) {
cout<<i.first<<" "<<i.second<<"\n";
}*/
while(value > 0 && dq.size()) {
if(dq.front().first < i - d) return false;
if(dq.front().second <= value) {
value -= dq.front().second;
dq.front().second = 0;
}
else {
dq.front().second -= value;
value = 0;
}
if(dq.front().second == 0) dq.pop_front();
}
/*cout<<"After processing: \n";
for(auto i:dq) {
cout<<i.first<<" "<<i.second<<"\n";
}
cout<<"--->\n";*/
}
return dq.size() == 0;
}
int main() {
cin>>n>>d>>m;
for(int i=1;i<=m;i++) {
cin>>x;
arr[x]++;
}
int li = 1, ri = m;
int answ = INT_MAX;
while(li < ri) {
int mid = (li+ri)/2;
if(check(mid)) ri = mid;
else li = mid + 1;
}
cout<<li<<"\n";
return 0;
}
Compilation message
jobs.cpp: In function 'int main()':
jobs.cpp:54:9: warning: unused variable 'answ' [-Wunused-variable]
int answ = INT_MAX;
^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
20 ms |
632 KB |
Unexpected end of file - int32 expected |
2 |
Incorrect |
19 ms |
632 KB |
Unexpected end of file - int32 expected |
3 |
Incorrect |
19 ms |
632 KB |
Unexpected end of file - int32 expected |
4 |
Incorrect |
19 ms |
632 KB |
Unexpected end of file - int32 expected |
5 |
Incorrect |
21 ms |
632 KB |
Unexpected end of file - int32 expected |
6 |
Incorrect |
20 ms |
632 KB |
Unexpected end of file - int32 expected |
7 |
Incorrect |
20 ms |
636 KB |
Unexpected end of file - int32 expected |
8 |
Incorrect |
20 ms |
632 KB |
Unexpected end of file - int32 expected |
9 |
Incorrect |
26 ms |
760 KB |
Unexpected end of file - int32 expected |
10 |
Incorrect |
26 ms |
504 KB |
Unexpected end of file - int32 expected |
11 |
Incorrect |
23 ms |
760 KB |
Unexpected end of file - int32 expected |
12 |
Incorrect |
42 ms |
1144 KB |
Output isn't correct |
13 |
Incorrect |
64 ms |
1516 KB |
Unexpected end of file - int32 expected |
14 |
Incorrect |
100 ms |
2424 KB |
Output isn't correct |
15 |
Incorrect |
103 ms |
2296 KB |
Unexpected end of file - int32 expected |
16 |
Incorrect |
210 ms |
3320 KB |
Unexpected end of file - int32 expected |
17 |
Incorrect |
174 ms |
3780 KB |
Unexpected end of file - int32 expected |
18 |
Incorrect |
166 ms |
3576 KB |
Unexpected end of file - int32 expected |
19 |
Incorrect |
199 ms |
3948 KB |
Unexpected end of file - int32 expected |
20 |
Incorrect |
175 ms |
3848 KB |
Unexpected end of file - int32 expected |