제출 #998264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
998264		MilosMilutinovic	추월 (IOI23_overtaking)	C++17	39 / 100	3568 ms	8464 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> w, s;
vector<vector<long long>> when;
long long x;

void init(int l, int N, vector<long long> t, vector<int> W, int X, int M, vector<int> S) {
  n = N; m = M; x = X; w = W; s = S;
  when = vector<vector<long long>>(m, vector<long long>(n));
  when[0] = t;
  for (int i = 1; i < m; i++) {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
      if (when[i - 1][a] != when[i - 1][b]) {
        return when[i - 1][a] < when[i - 1][b];
      } else {
        return w[a] < w[b];
      }
    });
    long long mx = 0;
    for (int j = 0; j < n; j++) {
      int b = order[j];
      mx = max(mx, when[i - 1][b] + w[b] * 1LL * (s[i] - s[i - 1]));
      when[i][b] = mx;
    }
  }
  return;
}

long long arrival_time(long long y) {
  for (int i = 0; i + 1 < m; i++) {
    long long t = y + x * 1LL * (s[i + 1] - s[i]);
    for (int j = 0; j < n; j++) {
      if (when[i][j] >= y) {
        continue;
      }
      t = max(t, when[i + 1][j]);
    }
    y = t;
  }
  return y;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35