Submission #1171913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171913		iah	Overtaking (IOI23_overtaking)	C++20	0 / 100	0 ms	840 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;

#define NAME ""
#define ll long long
#define pii pair < int , int >
#define pll pair < ll , ll >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

const int nmax = 1000;
int n, m, x;
ll f[nmax + 4][nmax + 4];
pll g[nmax + 4][nmax + 4];
vector < int > s;

void init(int l, int _n, std::vector<long long> t, std::vector<int> w, int _x, int _m, std::vector<int> _s) {
  n = _n;
  m = _m;
  x = _x;
  s = _s;

  REP(i, n) {
    f[i][0] = t[i];
  }

  vector < int > id(n, 0);
  iota(id.begin(), id.end(), 0);

  FOR(j, 1, m - 1) {
    sort(id.begin(), id.end(), [&] (const int &x, const int &y) {
      return ((f[x][j - 1] < f[y][j - 1]) || (f[x][j - 1] == f[y][j - 1] && w[x] < w[y]));
    });

    REP(x, n) {
      int i = id[x];
      f[i][j] = f[i][j - 1] + 1ll * (s[j] - s[j - 1]) * w[i];

      if (x > 0) {
        f[i][j] = max(f[i][j], f[id[x - 1]][j]);
      }
    }
  }

  FOR(j, 0, m - 2) {
    REP(i, n) {
      g[j][i] = {f[i][j], f[i][j + 1]};
    }
    sort(g[j], g[j] + n);

    FOR(i, 1, n - 1) {
      g[j][i].se = max(g[j][i].se, g[j][i - 1].se);
    }

//    REP(i, n) {
//      cout << g[j][i].se << " ";
//    }
//    cout << "\n";
  }
}

long long arrival_time(long long y) {
  f[n][0] = y;
  FOR(j, 0, m - 2) {
    f[n][j + 1] = f[n][j] + (s[j + 1] - s[j]) * x;
    int k = lower_bound(g[j], g[j] + n, pll{f[n][j], 0}) - g[j] - 1;

    if (k >= 0) {
      f[n][j + 1] = max(f[n][j + 1], g[j][k].se);
    }
  }

  return f[n][m - 1];
}

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