이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |