#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << endl
#define all(x) x.begin(),x.end()
int n,d,m;
pii a[1000010];
bool ok(int x)
{
int t=0,i=0,cnt=0,mx=0;
while(i<m)
{
while(i<m && cnt!=x && a[i].fi<=t) i++,cnt++,mx=max(mx,t+d);
cnt=0;
t++;
}
return mx<=n;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin>>n>>d>>m;
for(int i=0;i<m;i++) cin>>a[i].fi;
for(int i=0;i<m;i++) a[i].se=i;
sort(a,a+m);
int l=1,r=m,ans=m;
while(l<=r)
{
int mid=(l+r)/2;
if(ok(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans<<'\n';
// int t=1,i=0,cnt=0;
// while(i<m)
// {
// while(i<m && cnt!=ans && a[i].fi<=t)
// {
// cout<<a[i].se+1<<' ';
// i++,cnt++;
// }
// cnt=0;
// t++;
// cout<<"0\n";
// }
// while(t<=n)
// {
// t++;
// cout<<"0\n";
// }
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
2652 KB |
Output isn't correct |
2 |
Incorrect |
5 ms |
2692 KB |
Output isn't correct |
3 |
Incorrect |
8 ms |
2696 KB |
Output isn't correct |
4 |
Incorrect |
6 ms |
2652 KB |
Output isn't correct |
5 |
Incorrect |
6 ms |
2652 KB |
Output isn't correct |
6 |
Incorrect |
5 ms |
2700 KB |
Output isn't correct |
7 |
Incorrect |
6 ms |
2652 KB |
Output isn't correct |
8 |
Incorrect |
6 ms |
2652 KB |
Output isn't correct |
9 |
Incorrect |
11 ms |
2692 KB |
Output isn't correct |
10 |
Incorrect |
11 ms |
2652 KB |
Output isn't correct |
11 |
Incorrect |
11 ms |
2652 KB |
Output isn't correct |
12 |
Incorrect |
23 ms |
2652 KB |
Output isn't correct |
13 |
Incorrect |
35 ms |
4740 KB |
Output isn't correct |
14 |
Incorrect |
49 ms |
4744 KB |
Output isn't correct |
15 |
Incorrect |
57 ms |
4740 KB |
Output isn't correct |
16 |
Incorrect |
72 ms |
6740 KB |
Output isn't correct |
17 |
Incorrect |
86 ms |
6748 KB |
Output isn't correct |
18 |
Incorrect |
113 ms |
6780 KB |
Output isn't correct |
19 |
Incorrect |
107 ms |
7312 KB |
Output isn't correct |
20 |
Incorrect |
85 ms |
6528 KB |
Output isn't correct |