Submission #914191

#TimeUsernameProblemLanguageResultExecution timeMemory
914191mcdx9524Gym Badges (NOI22_gymbadges)C++17
0 / 100
411 ms39512 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Job { int deadline, duration, idx; bool operator<(Job o) const { return deadline < o.deadline; } }; vector<int> compute_schedule(vector<Job> jobs) { sort(jobs.begin(), jobs.end()); set<pair<int,int>> s; vector<int> schedule; for (int i = jobs.size()-1; i >= 0; i--) { int t = jobs[i].deadline - (i ? jobs[i-1].deadline : 0); s.insert(make_pair(jobs[i].duration, jobs[i].idx)); while (t && !s.empty()) { auto it = s.begin(); if (it->first <= t) { t -= it->first; schedule.push_back(it->second); } else { s.insert(make_pair(it->first - t, it->second)); t = 0; } s.erase(it); } } return schedule; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector <int> x(n), y(n); for (int i = 0; i < n; i++) { cin >> x[i]; } for (int i = 0; i < n; i++) { cin >> y[i]; } vector <Job> jobs; for (int i = 0; i < n; i++) { jobs.push_back({x[i] + y[i], y[i], i}); } auto ans = compute_schedule(jobs); cout << (int) ans.size() << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...