Submission #1043991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043991		juicy	Long Distance Coach (JOI17_coach)	C++17	100 / 100	83 ms	16980 KiB

coach

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;
const long long inf = 1e18;

struct line {
  long long a, b;

  long long eval(long long x) const {
    return a * x + b;
  }

  long long div(long long a, long long b) const { 
    return a / b - ((a ^ b) < 0 && a % b);
  }

  long long insec(const line &o) const {
    return div(o.b - b, a - o.a);
  }
};

int n, m, t, top;
long long x, w;
line hull[N];
long long pf[N], dp[N];
array<long long, 2> s[N], a[N];

void add(line k) {
  if (top > 0 && hull[top].a == k.a) {
    if (hull[top].b <= k.b) {
      return;
    }
    --top;
  }
  while (top > 1 && hull[top - 1].insec(hull[top]) >= hull[top].insec(k)) {
    --top;
  }
  hull[++top] = k;
}

long long qry(long long x) {
  int l = 1, r = top - 1, p = top;
  while (l <= r) {
    int md = (l + r) / 2;
    if (hull[md].insec(hull[md + 1]) >= x) {
      p = md;
      r = md - 1;
    } else {
      l = md + 1;
    }
  }
  return hull[p].eval(x);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> x >> n >> m >> w >> t;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i][1];
    s[i][0] = s[i][1] % t;
  }
  s[++n] = {x % t, x};
  for (int i = 1; i <= m; ++i) {
    cin >> a[i][0] >> a[i][1];
  }
  sort(s + 1, s + n + 1);
  sort(a + 1, a + m + 1);
  for (int i = 1; i <= m; ++i) {
    pf[i] = pf[i - 1] + a[i][1];
  }
  a[m + 1][0] = inf;
  add({0, 0});
  for (int i = 1, j = 0; i <= m; ++i) {
    dp[i] = dp[i - 1] + (x / t + ((x % t) >= a[i][0])) * w;
    long long mn = inf;
    while (j <= n && s[j][0] < a[i][0]) {
      ++j;
    }
    while (j <= n && s[j][0] < a[i + 1][0]) {
      mn = min(mn, s[j][1] / t);
      ++j;
    }
    if (mn != inf) {
      dp[i] = min(dp[i], qry(mn) + pf[i] + i * w * mn);
    }
    add({-i * w, dp[i] - pf[i]});
  }
  cout << dp[m] + (long long) (x / t + 1) * w;
  return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 29 / 29