Submission #292993

#	Time	Username	Problem	Language	Result	Execution time	Memory
292993		Autoratch	Job Scheduling (IOI19_job)	C++14	24 / 100	250 ms	19196 KiB

job

#include "job.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 1;

int n;
vector<int> adj[N];
priority_queue<pair<double,int> > q;
long long now,ans;

long long scheduling_cost(vector<int> p,vector<int> u,vector<int> d)
{
    n = p.size();
    for(int i = 0;i < n;i++) if(i) adj[p[i]].push_back(i);
    q.push({(double)u[0]/(double)d[0],0});
    while(!q.empty())
    {
        int x = q.top().second;
        q.pop();
        now+=d[x];
        ans+=now*u[x];
        for(int v : adj[x]) q.push({(double)u[v]/(double)d[v],v});
    }
    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