Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
3
Indexable
Never
#include <iostream>
using namespace std;

int n;
int ads[2][3]; // row 0: length of ads, row 1: points of ads
int cus[2][50]; // row 0: arrival time, row 1: staying time
int min_time;
int max_time;
int plan[2][3]; // row 0 : start time, row 2: end time
int kq;
void reset_plan(){
	for(int i = 0; i < 3; i++){
		plan[0][i] = plan[1][i] = 0;
	}
}

bool check(int st, int en){
	for(int i = 0; i < 3; i++){
		if(st > plan[0][i] && st < plan[1][i]) return false;
		if(en > plan[0][i] && en < plan[1][i]) return false;
		if(plan[0][i] > st && plan[0][i] < en) return false;
		if(plan[1][i] > st && plan[1][i] < en) return false;
	}
	return true;
}

void set(int st, int en, int k){
	plan[0][k] = st;
	plan[1][k] = en;
}
void unset( int k){
	plan[0][k] = 0;
	plan[1][k] = 0;
}
int cal_sum(){
	int sum = 0;
	for(int i = 0; i < n; i++){
		int max_point = 0;
		for(int j = 0; j < 3; j++){
			if(cus[0][i] <= plan[0][j] && cus[0][i] + cus[1][i] >= plan[1][j]) {
				if(ads[1][j] > max_point) max_point = ads[1][j];
			}
		}
		sum += max_point;
	}
	return sum;
}
void backtrack(int k){
	if(k == 3){
		int tmp_sum = cal_sum();
		if(tmp_sum > kq) kq = tmp_sum;
		return;
	}
	for(int i = min_time; i <= 50 - ads[0][k]; i++){
		if(check(i, i + ads[0][k])){
			set(i,i+ads[0][k],k);
			backtrack(k+1);
			unset(k);
		}
	}
}
int main(){
	freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> n;
		for(int i = 0; i < 3; i++){
			cin >> ads[0][i];
		}
		for(int i = 0; i < 3; i++){
			cin >> ads[1][i];
		}
		min_time = 100000;
		max_time = 0;
		for(int i = 0; i < n; i++){
			cin >> cus[0][i];
			cin >> cus[1][i];
			if(cus[0][i] < min_time) min_time = cus[0][i];
			if(cus[0][i] + cus[1][i] > max_time) max_time = cus[0][i] + cus[1][i];
		}
		kq = 0;
		reset_plan();
		backtrack(0);
		cout <<"Case #" <<tc << endl << kq << endl;
	}
	return 0;
}