Submission #709695

#	Time	Username	Problem	Language	Result	Execution time	Memory
709695		awu	Fuel Station (NOI20_fuelstation)	C++14	39 / 100	196 ms	27212 KiB

FuelStation

#include <bits/extc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#define int long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) do{auto y = x; cout << #x << " = " << y << endl;}while(0)
// #define endl "\n"
#define unordered_map __gnu_pbds::gp_hash_table
using pii = pair<int, int>;

const int inf = 1ll << 60;
const int MOD = 1e9 + 7;

struct fuel {
  int x, a, b;
};
bool operator<(fuel a, fuel b) {
  return a.x < b.x;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, d; cin >> n >> d;
  vector<fuel> fs(n);
  for(int i = 0; i < n; i++) {
    cin >> fs[i].x >> fs[i].a >> fs[i].b;
  }
  fs.push_back({d, 0, 0});
  sort(all(fs));
  auto bcmp = [](fuel a, fuel b) {
    return a.b > b.b;
  };
  priority_queue<fuel, vector<fuel>, decltype(bcmp)> pq(bcmp);
  int sf = 0, cf = 0, pos = 0;
  for(auto f : fs) {
    cf -= f.x - pos;
    pos = f.x;
    if(cf < 0) {
      sf -= cf;
      cf = 0;
      while(pq.size() && pq.top().b < sf) {
        sf += pq.top().a;
        pq.pop();
      }
    }
    if(sf < f.b) {
      cf += f.a;
      pq.push(f);
    }
  }
  cout << sf << endl;
}

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