Submission #1193796

#TimeUsernameProblemLanguageResultExecution timeMemory
1193796chaeryeongJob Scheduling (IOI19_job)C++20
12 / 100
128 ms24640 KiB
#include "job.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long long ld; const int MAXN = 2e5 + 25; //sum * d[i] + (sum - u[i]) * d[j] < sum * d[j] + (sum - u[j]) * d[i] //- u[i] * d[j] < -u[j] * d[i] //u[i] * d[j] > u[j] * d[i] //u[i] / d[i] > u[j] / d[j] when i is more optimal than j ll scheduling_cost(vector<int> p, vector<int> u, vector<int> d) { vector <int> adj[(int)p.size()]; for (int i = 0; i < (int)p.size(); i++) { if (p[i] != -1) { adj[p[i]].push_back(i); } } set <pair <ld, int>> ee; ee.insert({(ld)u[0] * 1.0 / d[0], 0}); vector <int> ans; while (!ee.empty()) { auto k = *(--ee.end()); ee.erase(k); ans.push_back(k.second); for (auto i : adj[k.second]) { ee.insert({(ld)u[i] * 1.0 / d[i], i}); } } ll sum = 0, ret = 0; for (auto i : ans) { sum += u[i]; } for (auto i : ans) { ret += sum * (ll)d[i]; sum -= u[i]; } return ret; }
#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...