Submission #1010609

#TimeUsernameProblemLanguageResultExecution timeMemory
1010609AnhPhamJob Scheduling (IOI19_job)C++17
21 / 100
3070 ms262144 KiB
// #include "job.h" #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] */ long long scheduling_cost(vector <int> p, vector <int> u, vector <int> d) { vector <vector <int>> adj(sz(p)); for (int i = 1; i < sz(p); ++i) adj[p[i]].emplace_back(i); auto Merge = [&](vector<int> a, vector<int> b) { int n = (int) a.size(), m = (int) b.size(); vector <long long> pfa(n + 1), pfb(m + 1); for (int i = 0; i < n; i++) { pfa[i + 1] = pfa[i] + d[a[i]]; } for (int i = 0; i < m; i++) { pfb[i + 1] = pfb[i] + d[b[i]]; } const long long inf = (long long) 1e18; vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, inf)); dp[0][0] = 0; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (i < n) { dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + (pfa[i + 1] + pfb[j]) * u[a[i]]); } if (j < m) { dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + (pfa[i] + pfb[j + 1]) * u[b[j]]); } } } vector<int> c; int x = n, y = m; while (x > 0 || y > 0) { if (x > 0 && dp[x][y] == dp[x - 1][y] + (pfa[x] + pfb[y]) * u[a[x - 1]]) { c.emplace_back(a[x - 1]); x--; } else if (y > 0 && dp[x][y] == dp[x][y - 1] + (pfa[x] + pfb[y]) * u[b[y - 1]]) { c.emplace_back(b[y - 1]); y--; } else { assert(false); } } reverse(c.begin(), c.end()); return c; }; vector <vector <int>> job(sz(p)); auto dfs = [&](auto &&self, int u) -> void { for (int v : adj[u]) { self(self, v); job[u] = Merge(job[u], job[v]); } job[u].insert(job[u].begin(), u); }; dfs(dfs, 0); long long tot_time = 0, ans = 0; for (int id : job[0]) { tot_time += d[id]; ans += tot_time * u[id]; } return ans; } // void solve() { // cout << scheduling_cost({ -1, 0, 0 }, { 5, 2, 5 }, { 3, 4, 1 }) << '\n'; // } // 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'; // }
#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...