Submission #1193800

#TimeUsernameProblemLanguageResultExecution timeMemory
1193800chaeryeongJob Scheduling (IOI19_job)C++20
24 / 100
66 ms17092 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); } } vector <int> ee; ee.push_back(0); vector <int> ans; while (!ee.empty()) { int k = ee.back(); ee.pop_back(); ans.push_back(k); for (auto i : adj[k]) { ee.push_back(i); } if (!adj[k].empty()) { sort(ee.begin(), ee.end(), [&] (auto i, auto j) { return (ll)u[i] * (ll)d[j] < (ll)u[j] * (ll)d[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...