Submission #649519

#TimeUsernameProblemLanguageResultExecution timeMemory
649519ShirleyMJob Scheduling (CEOI12_jobs)C++14
0 / 100
123 ms34508 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<bool> vb; typedef vector<vb> vvb; #define x first #define y second #define pb push_back #define loop(i,s,e) for(int i=s;i<e;i++) #define loopr(i,s,e) for(int i=e-1; i>=s;i--) #define chkmax(a,b) a=max(a,b) #define chkmin(a,b) a=min(a,b) #define all(a) a.begin(),a.end() #define fast {ios_base::sync_with_stdio(0); cin.tie(0);} const int inf = 1e18; const int INF = 1e9; int n, d, m; vi tasks; vvi starts_in, ends_in; vvi t_per_day; bool ok(int k){ loop(i,1,n+1) t_per_day[i].clear(); vi cur_tasks; vb vis(m); int cnt=0, done=0, closed=0; loop(i,1,n+1){ cnt+=starts_in[i].size(); done+=k; if(done > cnt) done=cnt; closed += ends_in[i].size(); if(done < closed) return 0; } return 1; } int32_t main() { fast; cin >> n >> d >> m; starts_in.resize(n+1); ends_in.resize(n+1); tasks.resize(m); t_per_day.resize(n+1); loop(i,0,m){ cin >> tasks[i]; int s=tasks[i], e=s+d; starts_in[s].pb(i); ends_in[e].pb(i); } int l=0, r=m, mid, ans=-1; while(l<=r){ mid = (l+r)/2; if(ok(mid)){ ans = mid; r = mid-1; } else l = mid+1; } /*deque<int> cur_tasks; loop(i,1,n+1){ for(int t:starts_in[i]){ cur_tasks.pb(t); } loop(j,0,ans){ t_per_day[i].pb(cur_tasks.front()); cur_tasks.pop_front(); } }*/ cout << ans << endl; /*loop(i,1,n+1){ for(int t:t_per_day[i]) cout << t<< " "; cout << "0\n"; }*/ return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...