Submission #202614

#	Time	Username	Problem	Language	Result	Execution time	Memory
202614		anonymous	Job Scheduling (IOI19_job)	C++14	24 / 100	185 ms	21468 KiB

job

#include "job.h"
#include <vector>
#include<queue>
#include<utility>
#include<iostream>
#define LL long long
#define MAXN 300005
using namespace std;
struct Job {LL wt, t, id;};
class CompareClass {
public:
    bool operator() (Job a, Job b) {
        return(a.wt*b.t > a.t*b.wt); //wt, time
    }
};
int chd[MAXN], N;
priority_queue<Job ,vector<Job>, CompareClass> PQ;
vector<Job> Order;
LL scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
	N=p.size();
	for(int i=1; i<N; i++) {
        chd[p[i]]++;
	}
	for (int i=0; i<N; i++) {
        if (!chd[i]) {
            PQ.push(Job {u[i], d[i], i});
        }
	}
	while (Order.size() < N) {
        Job opt = PQ.top();
        PQ.pop();
        Order.push_back(opt);
        if (opt.id == 0) {break;}
        chd[p[opt.id]]--;
        if (!chd[p[opt.id]]) {
            PQ.push(Job {u[p[opt.id]], d[p[opt.id]], p[opt.id]});
        }
	}
	LL ans=0, time=0;
	for (int i=N-1; i>=0; i--) {
        time+=Order[i].t;
        ans+=Order[i].wt*time;
	}
	return(ans);
}

Compilation message (stderr)

job.cpp: In function 'long long int scheduling_cost(std::vector<int>, std::vector<int>, std::vector<int>)':
job.cpp:29:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (Order.size() < N) {
         ~~~~~~~~~~~~~^~~

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