Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
1
Indexable
Never
#include <iostream>

using namespace std;
#define maxn 51
int n, ans;
int adv[3][2];
int client[maxn][2];
int visa[3];
int jav[3][2];
void imports(){
	cin >> n;
	for(int i = 0; i < 3; i++){
		cin >> adv[i][0];
	}
	for(int i = 0; i < 3; i++){
		cin >> adv[i][1];
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 2; j++){
			cin >> client[i][j];
		}
	}
}

void reset(){
	for(int i = 0; i < 3; i++){
		visa[i] = 0;
		for(int j = 0; j < 2; j++){
			adv[i][j] = 0;
			jav[i][j] = 0;
		}
	}
	for(int i = 0; i < maxn; i++){
		for(int j = 0; j < 2; j++){
			client[i][j] = 0;
		}
	}
}

bool check_pos(int a, int pos){
	int end = pos + adv[a][0];
	for(int i = 0; i < 3; i++){
		if(pos <= jav[i][0] && end > jav[i][0])
			return false;
		if(pos > jav[i][0] && pos < jav[i][1])
			return false;
		if(end > jav[i][0] && end < jav[i][1])
			return false;
	}
	return true;
}

void backtrack(int qc){
	if( qc == 3){
		int sum = 0;
		for(int i = 0; i < n; i++){
			int point = 0;
			int start = client[i][0];
			int end = client[i][0] + client[i][1] ;
			for(int j = 0; j < 3; j ++){
				if(start <= jav[j][0] && end >= jav[j][1] && adv[j][1] > point){
					point = adv[j][1];
				}
			}
			sum += point;
		}
		if( sum > ans){
			ans = sum;
		}
		return;
	}

	for(int i = 1; i <= 50; i++){
		if(check_pos(qc, i)){
			jav[qc][0] = i;
			jav[qc][1] = i + adv[qc][0];
			backtrack(qc + 1);
			jav[qc][0] = 0;
			jav[qc][1] = 0;
		}
	}

}

void exports(int tc){
	ans = 0;
	backtrack(0);
	cout << "Case #" << tc << endl;
	cout << ans << endl;
}

int main(){
	freopen("input.txt","r",stdin);
	int t;
	cin >> t;
	for(int tc = 1; tc <= t; tc++){
		reset();
		imports();
		exports(tc);
	}
	return 0;
}