Untitled

mail@pastecode.io avatar
unknown
plain_text
24 days ago
1.0 kB
5
Indexable
Never
#include <iostream>

using namespace std;
int T, P, dis;
int mins[5];
int seconds[5];
int timeR[5];
int pows[5];
int min_time, tmp, power;
void backtrack(int k, int d){
	if(tmp >= min_time){
		return;
	}
	if(power > P){
		return;
	}
	if(d == dis){
		if(tmp < min_time){
			min_time = tmp;
		}
		return;
	}

	for(int i = k; i < 5; i++){
		tmp += timeR[i];
		power += pows[i];
		backtrack(i, d + 1);
		tmp -= timeR[i];
		power -= pows[i];
	}
}

int main(){
	freopen("input.txt", "rt", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> P >> dis;
		for(int i = 0; i < 5; i++){
			cin >> mins[i] >> seconds[i] >> pows[i];
			timeR[i] = mins[i] * 60 + seconds[i];
		}
		tmp = 0;
		min_time = 10000000;
		power = 0;
		backtrack(0, 0);
		cout << "Case #" << tc << endl;
		if(min_time == 10000000){
			cout << -1 << endl;
		}else{
			int mins = min_time / 60;
			int ses = min_time % 60;
			cout << mins <<" "<< ses << endl;
		}
	}
	return 0;
}
Leave a Comment