제출 #1039833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039833		abczz	Long Distance Coach (JOI17_coach)	C++17	100 / 100	223 ms	20628 KiB

coach

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long
#define ld long double

using namespace std;

array <ll, 2> A[200000];
vector <ll> V;
ll mn[200000], ps[200000];
ll x, n, m, w, t, p, a, b, l, r, mid, S[200001], dp[200000];
ld ep = 1e-8, z;
struct Line{
  ll m;
  ll c;
};
ld intx(Line I, Line J) {
  return (ld)(I.c-J.c)/(J.m-I.m);
}
vector <Line> L;
int main() {
  cin >> x >> n >> m >> w >> t;
  for (int i=0; i<n; ++i) {
    cin >> S[i];
  }
  S[n] = x;
  sort(S, S+n+1);
  for (int i=0; i<m; ++i) {
    cin >> A[i][0] >> A[i][1];
  }
  sort(A, A+m);
  for (int i=0; i<m; ++i) {
    V.push_back(A[i][0]);
    mn[i] = 1e18;
    ps[i] = (i ? ps[i-1] : 0) + A[i][1];
  }
  for (int i=0; i<=n; ++i) {
    auto it = lower_bound(V.begin(), V.end(), S[i] % t);
    if (it != V.begin()) {
      it = prev(it);
      mn[it-V.begin()] = min(mn[it-V.begin()], S[i] / t);
    }
  }
  L.push_back({w, 0});
  for (ll i=0; i<m; ++i) {
    dp[i] = (i ? dp[i-1] : 0) + (ll)((x-A[i][0]) / t + 1) * w;
    if (mn[i] != 1e18) {
      l = 0, r = L.size()-1;
      while (l < r) {
        mid = (l+r+1)/2;
        if (!mid) x = 0;
        else z = intx(L[mid-1], L[mid]);
        if ((ld)mn[i]-z >= -ep) l = mid;
        else r = mid-1;
      }
      dp[i] = min(dp[i], L[l].m * mn[i] + L[l].c + mn[i] * w * i + ps[i]);
    }
    Line nw = {-i * w, dp[i] - ps[i]};
    while (L.size() >= 2) {
      auto I = L.back();
      auto J = L[L.size()-2];
      if (intx(J, I)-intx(J, nw) >= -ep) L.pop_back();
      else break;
    }
    L.push_back(nw);
  }
  cout << dp[m-1] + (x/t+1) * w << '\n';
}

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