Submission #866444

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
866444	2023-10-26 07:46:49	SorahISA	Job Scheduling (IOI19_job)	C++17	100 / 100	365 ms	39764 KiB

job

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "job.h"
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
struct Job {
    int64 u, d, id;
    Job(int64 _u, int64 _d, int64 _id) : u(_u), d(_d), id(_id) {}
    bool operator < (const Job &rhs) const {
        return d * rhs.u < rhs.d * u;
    }
};
int64 scheduling_cost(vector<int> p, vector<int> u, vector<int> d) {
    int N = p.size();
    vector<set<int>> ch(N);
    for (int i = 1; i < N; ++i) ch[p[i]].emplace(i);
    
    multiset<Job> jobs;
    for (int i = 0; i < N; ++i) jobs.emplace(u[i], d[i], i);
    
    int64 tim = 0, ans = 0;
    while (jobs.size()) {
        
        Job job = *begin(jobs);
        jobs.erase(begin(jobs));
        
        // cerr << "(" << job.u << ", " << job.d << ", " << job.id << ")\n";
        if (u[job.id] != job.u or d[job.id] != job.d) continue;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 37 / 37