Submission #843722

#	Time	Username	Problem	Language	Result	Execution time	Memory
843722		flashmt	Overtaking (IOI23_overtaking)	C++17	65 / 100	3516 ms	71212 KiB

overtaking

#include "overtaking.h"
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

long long t[N][N];
int n, m,reserveSpeed;
vector<int> stops;
map<long long, long long> boundMap[N];

void init(int L, int n_, vector<long long> t0, vector<int> speed, int reserveSpeed_, int m_, vector<int> stops_)
{
  n = n_; m = m_;
  stops = stops_;
  reserveSpeed = reserveSpeed_;
  for (int i = 0; i < n; i++)
    t[0][i] = t0[i];
  for (int i = 0; i < m - 1; i++)
  {
    vector<int> orders(n);
    iota(begin(orders), end(orders), 0);
    sort(begin(orders), end(orders), [&](int u, int v) { return t[i][u] < t[i][v]; });

    long long bound = 0;
    boundMap[i][-1] = 0;
    for (int j = 0; j < n;)
    {
      long long curT = t[i][orders[j]];
      long long newBound = bound;
      while (j < n && t[i][orders[j]] == curT)
      {
        int id = orders[j++];
        t[i + 1][id] = max(bound, t[i][id] + 1LL * speed[id] * (stops[i + 1] - stops[i]));
        newBound = max(newBound, t[i + 1][id]);
      }
      bound = newBound;
      boundMap[i][curT] = bound;
    }
  }
  return;
}

long long arrival_time(long long t0)
{
  auto curT = t0;
  for (int i = 0; i < m - 1; i++)
  {
    auto u = boundMap[i].lower_bound(curT);
    auto bound = (--u)->second;
    curT += 1LL * reserveSpeed * (stops[i + 1] - stops[i]);
    curT = max(curT, bound);
  }
  return curT;
}

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