Submission #417356

#	Time	Username	Problem	Language	Result	Execution time	Memory
417356		rama_pang	Job Scheduling (IOI19_job)	C++17	19 / 100	91 ms	8112 KiB

job

#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];
  }

	return ans;
}

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