제출 #313666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
313666		MiricaMatei	Job Scheduling (IOI19_job)	C++14	24 / 100	152 ms	19324 KiB

job

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200005;

vector<int>G[MAXN];

struct Obj {
  int i, u, d;
  bool operator <(const Obj& other) const {
    bool ans;
    if (u == 0) {
      ans = 0;
    } else {
      if (other.u == 0) {
        ans = 1;
      } else {
        if (1LL * d * other.u < 1LL * other.d * u)
          ans = 1;
        else
          ans = 0;
      }
    }
    return !ans;
  }
};

long long scheduling_cost(vector<int>p, vector<int>u, vector<int>d) {
  int n = p.size();
  for (int i = 1; i < n; ++i)
    G[p[i]].push_back(i);
  long long ans = 0;
  long long t = 0;
  priority_queue<Obj>pq;
  pq.push({0, u[0], d[0]});
  while (!pq.empty()) {
    Obj aux = pq.top();
    pq.pop();
    t += aux.d;
    ans += t * aux.u;
    for (auto it:G[aux.i])
      pq.push({it, u[it], d[it]});
  }
  return ans;
}

/*int main() {
  freopen("date.in", "r", stdin);
  freopen("date.out", "w", stdout);

  int n;
  scanf("%d", &n);
  vector<int>p(n), u(n), d(n);
  for (int i = 0; i < n; ++i)
    scanf("%d", &p[i]);
  for (int i = 0; i < n; ++i)
    scanf("%d", &u[i]);
  for (int i = 0; i < n; ++i)
    scanf("%d", &d[i]);

  printf("%lld\n", scheduling_cost(p, u, d));

  return 0;
}*/

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