제출 #417356

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
417356	2021-06-03 15:19:27	rama_pang	Job Scheduling (IOI19_job)	C++17	19 / 100	91 ms	8112 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]
  int n = p.size();
  lint ans = 0;
  vector<int> ord(n);
  iota(begin(ord), end(ord), 0);
  sort(begin(ord) + 1, end(ord), [&](int i, int j) {
    return u[i] * d[j] > u[j] * d[i];
  });
  int t = 0;
  for (auto i : ord) {
    t += d[i];
    ans += 1ll * t * u[i];
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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