Submission #651047

#	Time	Username	Problem	Language	Result	Execution time	Memory
651047		dsyz	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	166 ms	24740 KiB

FuelStation

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,D;
	cin>>N>>D;
	N++;
	pair<ll,pair<ll,ll> > arr[N];
	for(ll i = 0;i < N - 1;i++){
		cin>>arr[i].first>>arr[i].second.first>>arr[i].second.second;
	}
	arr[N - 1].first = D, arr[N - 1].second.first = 0, arr[N - 1].second.second = 0;
	ll F = 0;
	ll cur = 0; //F + all A[i]
	sort(arr,arr + N);
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
	for(ll i = 0;i < N;i++){
		if(cur < arr[i].first){
			F += arr[i].first - cur;
			cur = arr[i].first;
		}
		while(!pq.empty() && pq.top().first < F){
			cur -= pq.top().second;
			pq.pop();
			if(cur < arr[i].first){
				F += arr[i].first - cur;
				cur = arr[i].first;
			}
		}
		if(F <= arr[i].second.second){
			cur += arr[i].second.first;
			pq.push(make_pair(arr[i].second.second,arr[i].second.first));
		}
	}
	cout<<F<<'\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