Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.9 kB
1
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

int Time[3][2], adv[3][2];
int point[52], arrival[52], duaration[52];
int nTestcase, N, P1, P2, P3, Maxpoint;

bool check(int k, int t) {
	if (k == 0) return true;
	if (k == 1) {
		if (t < Time[0][0] && t + adv[1][0] > Time[0][0]) return false;
		if (t >= Time[0][0] && t < Time[0][1]) return false;
	}
	if (k == 2) {
		if (t < Time[0][0] && t + adv[2][0] > Time[0][0]) return false;
		if (t >= Time[0][0] && t < Time[0][1]) return false;
		//
		if (t < Time[1][0] && t + adv[2][0] > Time[1][0]) return false;
		if (t >= Time[1][0] && t < Time[1][1]) return false;
	}
	return true;
}

void resetPoint() {
	for (int i = 0; i < N; i++) {
		point[i] = 0;
	}
}

int findScore() {
	resetPoint();
	int temp, sum;
	for (int i = 0; i < N; i++) {
		int start = arrival[i];
		int end = start + duaration[i];
		for (int j = 0; j < 3; j++) {
			if (start <= Time[j][0] && end >= Time[j][1]) {
				temp = adv[j][1];
				point[i] = point[i] < temp ? temp : point[i];
			}
		}
	}
	sum = 0;
	for (int i = 0; i < N; i++) {
		sum += point[i];
	}
	return sum;
}

void backtrack(int k) {
	if (k == 3) {
		int sum = findScore();
		Maxpoint = Maxpoint > sum ? Maxpoint : sum;
		return;
	}
	for (int i = 1; i < 50; i++) {
		if (check(k, i)) {
			Time[k][0] = i;
			Time[k][1] = i + adv[k][0];
			backtrack(k + 1);
			Time[k][0] = 0;
			Time[k][1] = 0;
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	cin >> nTestcase;
	for (int testcase = 1; testcase <= nTestcase; testcase++) {
		cin >> N >> adv[0][0] >> adv[1][0] >> adv[2][0] >> adv[0][1] >> adv[1][1] >> adv[2][1];
		Maxpoint = 0;
		for (int i = 0; i < N; i++) {
			cin >> arrival[i] >> duaration[i];
			point[i] = 0;
		}
		backtrack(0);
		cout << "Case #" << testcase << endl << Maxpoint << endl;
	}
	return 0;
}
Leave a Comment