Untitled

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

int N;
int qc[4];// do dai cua quang cao
int sc[4];// diem so

int A[51]; // thoi gian khach hang bat dau den
int D[51]; // khoang thoi gian khach hang o lai

int tim[4][2]; // quang cao thi k co time bat dai time[k][0] va thoi gian kt time[k][1]

void reset()
{
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 2; j++)
		{
			tim[i][j] = 0;
		}
	}
}

// tinh diem so xem quang cao khi da xem du 3 quang cao
int scc()
{
	int diem[51] = { 0 }; //diem so khack hang nhan duoc
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= 3; j++)
		{
			int xbgin = tim[j][0];
			int xend = tim[j][1];
			if (A[i] <= xbgin && A[i] + D[i] >= xend)
			{
				if (diem[i] < sc[j])
				{
					diem[i] = sc[j];
				}
			}
		}
	}
	int sum = 0;
	for (int i = 1; i <= N; i++)
	{
		sum = sum + diem[i];
	}
	return sum;
}

// kiem tra xem quang cao thu k duoc dat vao vi tri i co bi trung hay khong
bool check(int k, int bgin)
{
	int end = bgin + qc[k];
	for (int i = 1; i <= 3; i++)
	{
		if (tim[i][0] != 0 && tim[i][1] != 0 && i != k)
		{
			// time1 la time bat dau time2 la kt
			if (bgin <= tim[i][0] && tim[i][1] <= end) // phai nho hon bang vi tai hai thoi dien deu bang nhau khong thoa man
			{
				return false;
			}
			if (tim[i][0] <= bgin && bgin < tim[i][1] && tim[i][1] < end)
			{
				return false;
			}
			if (bgin <= tim[i][0] && tim[i][0] < end && end < tim[i][1])
			{
				return false;
			}
			if (tim[i][0] <=bgin && end <= tim[i][1]) // phai nho hon bang vi x0 , y0 name ben trong phan tu
			{
				return false;
			}
		}
	}
	return true;
}


void quangcao(int& max, int k)
{
	if (k == 4)
	{
		int t = scc();
		if (max < t)
		{
			max = t;
		}
		return;
	}
	// chon thoi diem chieu cua quang cao
	for (int i = 1; i <= 50; i++)
	{
		if (check(k, i) == true)
		{
			tim[k][0] = i;
			tim[k][1] = i + qc[k];
			quangcao(max, k + 1);
			tim[k][0] = 0;
			tim[k][1] = 0;
		}
	}
}


int main()
{
	//freopen("input.txt", "r", stdin);
	int testcase;
	cin >> testcase;
	for (int tc = 1; tc <= testcase; tc++)
	{
		cin >> N;
		for (int i = 0; i < 51; i++)
		{
			A[i] = 0;
			D[i] = 0;
		}
		reset();
		for (int i = 1; i <= 3; i++)
		{
			cin >> qc[i];  // do dai cua quang cao thu i
		}
		for (int i = 1; i <= 3; i++)
		{
			cin >> sc[i]; // diem so cua quang cao thu i
		}
		// thoi gian den va di
		for (int i = 1; i <= N; i++)
		{
			cin >> A[i];
			cin >> D[i];
		}
		int max = 0;
		quangcao(max, 1);
		cout << "Case #" << tc << endl << max << endl;
	}
}