Submission #1060773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060773		vjudge1	Job Scheduling (IOI19_job)	C++17	24 / 100	70 ms	12228 KiB

job

#include "job.h"
#include <bits/stdc++.h>
using namespace std;
struct DATA{
    int timetaken,value,i;
    DATA(int u,int d,int ind){
        value=u,timetaken=d,i=ind;
    }
    DATA(){
        timetaken=1e9;
        value=1;
    }
    friend bool operator<(const DATA &a,const DATA&b){
        return a.timetaken*b.value<
                b.timetaken*a.value;
    }
};
priority_queue<DATA>pq;
vector<int>ord;
int deg[1<<18];
long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
    int N=p.size();
    for(int i=1;i<N;i++)
        deg[p[i]]++;
    for(int i=0;i<N;i++) if(!deg[i])
        pq.push(DATA(u[i],d[i],i));
    while(pq.size()){
        int K=pq.top().i;
        pq.pop();
        if(!--deg[p[K]])
            pq.push(DATA(u[p[K]],d[p[K]],p[K]));
        ord.push_back(K);
    }
    reverse(ord.begin(),ord.end());
    long long curtime=0,ans=0;
    for(auto i:ord)
        ans+=u[i]*(curtime+=d[i]);
    ord.clear();
    return ans;
}

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