Submission #417399

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
417399	2021-06-03 16:18:25	rama_pang	Job Scheduling (IOI19_job)	C++17	100 / 100	399 ms	74208 KiB

job

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "job.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
lint scheduling_cost(vector<int> P, vector<int> U, vector<int> D) {
  // Solution:
  // Assume there is no p[]. Let's ignore u[i] * d[i].
  //
  // Let's observe i and j. If i < j is optimal:
  // u[j] * d[i] < u[i] * d[j]
  // u[j] / d[j] < u[i] / d[i]
  // So, we sort by u[x] / d[x] in decreasing opt.
  // With this, we can solve for a star graph.
  //
  // Now, assume it's a tree, and we only have 2 children.
  // If the optimal ordering of the children is sorted
  // decreasingly by U[i] / D[i], then we can merge the
  // sorted list together.
  //
  // Assume we have a list = {U[i] / D[i], U[j] / D[j]} and {U[k] / D[k]}.
  // Also, U[i] / D[i] < U[j] / D[j].
  //
  // Since j comes after i, let's ignore U[j] * D[i].
  //
  // Cost if {i, j, k}:
  // U[k] * D[i] + U[k] * D[j]
  //
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 37 / 37