| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1010390 | AnhPham | Job Scheduling (IOI19_job) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#ifdef OP_DEBUG
#include <algo/debug.h>
#else
#define debug(...) 26
#endif
using namespace std;
#define int long long
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define TcT template <class T
const int MOD = (int)1e9 + 7, INF = (int)4e18 + 18;
TcT> bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
TcT> bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }
void solve();
int32_t main() {
cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
int testcases = 1;
#define TC 0
if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}
/* [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] */
struct Info {
int id;
int w, t;
bool operator < (const Info &other) const {
return w * other.t < other.w * t;
}
};
int scheduling_cost(vector <int> p, vector <int> u, vector <int> d) {
int n = sz(p);
vector <vector <int>> adj(n);
for (int i = 1; i < n; ++i)
adj[p[i]].emplace_back(i);
int tot_time = 0, ans = 0;
priority_queue <Info> pq; pq.push({ 0, u[0], d[0] });
while (sz(pq)) {
Info job = pq.top(); pq.pop();
tot_time += d[job.id];
ans += tot_time * u[job.id];
for (int v : adj[job.id])
pq.push({ v, u[v], d[v] });
}
return ans;
}
// void solve() {
// int n; cin >> n;
// vector <int> P(n), W(n), T(n);
// for (int &p : P)
// cin >> p;
// for (int &w : W)
// cin >> w;
// for (int &t : T)
// cin >> t;
// vector <vector <int>> adj(n);
// for (int i = 1; i < n; ++i)
// adj[P[i]].emplace_back(i);
// int tot_time = 0, ans = 0;
// priority_queue <Info> pq; pq.push({ 0, W[0], T[0] });
// while (sz(pq)) {
// Info job = pq.top(); pq.pop();
// tot_time += T[job.id];
// ans += tot_time * W[job.id];
// for (int v : adj[job.id])
// pq.push({ v, W[v], T[v] });
// }
// cout << ans << '\n';
// }