Submission #1241416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241416		mychecksedad	Overtaking (IOI23_overtaking)	C++17	65 / 100	3594 ms	47536 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define ll long long int
const int N = 2000;


ll dp[N][N], X;
pair<ll, ll> pref[N][N];
int n, m;
vi W, S;
vector<ll> T;
void init(int L, int nn, std::vector<long long> TT, std::vector<int> WW, int XX, int mm, std::vector<int> SS)
{
  X = XX;
  S = SS;
  W = WW;
  T = TT;
  n = nn;
  m = mm;
  W.pb(X);
  for(int i = 0; i < n; ++i) dp[0][i] = T[i];
  for(int i = 1; i < m; ++i){
    ll dif = S[i] - S[i - 1];
    vector<pair<ll, int>> q;
    for(int j = 0; j < n; ++j) q.pb({dp[i-1][j], j});
    sort(all(q));
    ll last = 0ll, last2 = 0ll;
    for(int j = 0; j < n; ++j){
      int p = q[j].ss;
      dp[i][p] = max(last, dp[i - 1][p] + dif * W[p]);
      last2 = max(last2, dp[i][p]);
      if(j + 1 < n && q[j+1].ff != q[j].ff) last=max(last,last2);
    }
    pref[i-1][0] = {q[0].ff, dp[i][q[0].ss]};
    for(int j = 1; j < n; ++j){
      pref[i-1][j].ff = q[j].ff;
      pref[i-1][j].ss = max(
        pref[i-1][j-1].ss,
        dp[i][q[j].ss]
      );
    }
  }
  return;
}

long long arrival_time(long long Y)
{
  T.pb(Y);
  ll cur = Y;
  for(int i = 0; i + 1 < m; ++i){
    ll nxt = cur + (S[i + 1] - S[i]) * X;
    int pos = lower_bound(pref[i], pref[i] + n, pair<ll, ll>{cur, -1}) - pref[i];
    --pos;
    if(pos >= 0) nxt = max(nxt, pref[i][pos].ss);
    cur = nxt;
  }
  T.pop_back();
  return cur;
}

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