Submission #1290273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290273		lucian	Fuel Station (NOI20_fuelstation)	C++20	37 / 100	3096 ms	12892 KiB

FuelStation

#include <bits/stdc++.h>
#define int long long

using namespace std;
struct station{
	int x;
	int a;
	int b;
}; 

int n, d, answer;
vector<station> arr;
int x1, a1, b1;

bool cmp(const station &s1, const station &s2) {
    return s1.x < s2.x;
}

bool check(int f){
	int fuel = f;
	int pos = 0;
//	cout << "STARTING WITH " << f << endl;
	for(int i = 0; i <= n - 1; i++){
		fuel = fuel - (arr[i].x - pos);
		if(fuel < 0){
			return false;
		}
		if(f <= arr[i].b){
			fuel = fuel + arr[i].a;
		}
		pos = arr[i].x;
//		cout << fuel << " ";
	}
//	cout << endl << endl;
    return fuel >= 0;
}
	
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> d;
	for(int i = 1; i <= n; i++){
		cin >> x1 >> a1 >> b1;
		arr.push_back({x1, a1, b1});
	}
	if (n == 1) {
	    int x = arr[0].x, a = arr[0].a, b = arr[0].b;
	    int need = max(x, d - a);
	    if (need <= b){
	    	cout << need;
		} else{
			cout << d;
		}
	    return 0;
	}

	sort(arr.begin(), arr.end(), cmp);
//	for(int i = 0; i <= n - 1; i++){
//		cout << arr[i].x << " " << arr[i].a << " " << arr[i].b << endl;
//	
	
	for(int i = 1; i <= d; i++){
		if(check(i)){
			cout << i;
			return 0;
		}
	}
}

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