Submission #1163684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163684		avighna	Fuel Station (NOI20_fuelstation)	C++20	100 / 100	170 ms	21556 KiB

FuelStation

#include <bits/stdc++.h>

typedef long long ll;

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

  ll n, d;
  std::cin >> n >> d;
  struct Station {
    ll x, a, b;
  };
  std::vector<Station> a(n);
  std::set<ll> b_vals;
  for (auto &i : a) {
    std::cin >> i.x >> i.a >> i.b;
    b_vals.insert(i.b);
  }
  std::sort(a.begin(), a.end(), [](Station a, Station b) { return a.x < b.x; });

  auto f = [&](ll F) {
    ll fuel = 0, pos = 0, ans = F;
    for (ll i = 0; i < n; ++i) {
      fuel -= a[i].x - pos;
      ans = std::min(ans, fuel);
      fuel += a[i].a * (F <= a[i].b);
      pos = a[i].x;
    }
    return -std::min(ans, fuel - (d - pos));
  };

  ll ans = d, prev = 0;
  // fix the number of activated stations
  for (auto &b : b_vals) {
    if (b < prev) {
      continue;
    }
    ll val = f(b);
    if (val <= b) {
      ans = val;
      break;
    }
    prev = val;
  }
  std::cout << ans << '\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 12 / 12
• Subtask 5: 19 / 19
• Subtask 6: 11 / 11
• Subtask 7: 21 / 21