Submission #1171912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171912		iah	Overtaking (IOI23_overtaking)	C++20	39 / 100	3592 ms	8320 KiB

overtaking

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

#define NAME ""
#define ll long long
#define pii pair < int , int >
#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];
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]);
      }
    }
  }
}

long long arrival_time(long long y) {
  f[n][0] = y;
  FOR(j, 1, m - 1) {
    f[n][j] = f[n][j - 1] + 1ll * (s[j] - s[j - 1]) * x;
    REP(i, n) {
      if (f[i][j - 1] < f[n][j - 1]) {
        f[n][j] = max(f[n][j], f[i][j]);
      }
    }

//    FOR(i, 0, n) {
//      cout << f[i][j] << " ";
//    }
//    cout << "\n";
  }

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

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