Submission #1060767

#TimeUsernameProblemLanguageResultExecution timeMemory
1060767boyliguanhanJob Scheduling (IOI19_job)C++17
0 / 100
1 ms348 KiB
#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; } }; long long scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) { int N=p.size(); vector<int>ord,deg(N); priority_queue<DATA>pq; 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]); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...