Submission #934411

#TimeUsernameProblemLanguageResultExecution timeMemory
934411tamir1Job Scheduling (CEOI12_jobs)C++14
0 / 100
144 ms16828 KiB
#include<bits/stdc++.h> #define ff first #define ss second #define ll long long using namespace std; ll i,n,d,m,l,r,mid,ans; pair<ll,ll> a[1000005]; bool check(ll mid){ ll i=1,j,day=0; while(i<=m){ day++; for(j=i;j<i+mid && j<=m;j++){ if(day>a[j].ff+d) return 0; } i=j; } if(day>n) return 0; return 1; } /*void solve(ll x){ ll i,j,idx,day=0; for(i=1;i<=m;){ day++; idx=0; for(j=i;j<i+x && j<=m;j++){ if(a[j].ff<day) break; idx=max(idx,j); } i=idx+1; cout << i << " "; //cout << 0 << "\n"; } }*/ int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> d >> m; for(i=1;i<=m;i++){ cin >> a[i].ff; a[i].ss=i; } sort(a+1,a+m+1); l=1; r=m; while(r-l>1){ mid=(r+l+1)/2; if(check(mid)) r=mid; else l=mid; } if(check(l)) ans=l; else ans=r; cout << ans << "\n"; //solve(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...