CF254B Jury Size

题目翻译

CF254B 评审团人数

题目描述

在2013年，伯兰德州立大学的出题者需要为 $n$ 场奥林匹克竞赛准备题目。我们假定这些奥林匹克竞赛用从1到 $n$ 的连续整数编号。对于每一场奥林匹克竞赛，我们知道需要多少评审团成员参与其题目准备工作，以及准备该竞赛题目所需的时间。具体来说，第 $i$ 场奥林匹克竞赛需要 $p_i$ 个人花费 $t_i$ 天来准备，并且准备工作应该是一个连续的时间段，且恰好要在竞赛开始的前一天结束。在竞赛当天，已经准备好该竞赛的评审团成员就不再为这场竞赛工作了。

例如，如果一场奥林匹克竞赛在12月9日举行，且准备工作需要7个人花费6天时间，那么所有7名评审团成员将从12月3日到12月8日为这场奥林匹克竞赛的题目工作（评审团成员在12月9日不会为这场奥林匹克竞赛的题目工作，也就是说，他们中的一些人可以开始为其他某场奥林匹克竞赛准备题目）。而如果一场奥林匹克竞赛在11月3日举行，且需要5天的准备时间，评审团成员将从10月29日到11月2日进行工作。

为了避免评审团负担过重，引入了以下规则：一名评审团成员不能在同一天为不同的奥林匹克竞赛的题目工作。编写一个程序，确定评审团中最少需要多少人，才能按时准备好所有的奥林匹克竞赛。

输入格式

第一行包含整数 $n$ —— 2013年奥林匹克竞赛的数量（$1\le n\le 100$）。接下来的 $n$ 行，每行包含四个整数 $m_i$ 、$d_i$ 、$p_i$ 和 $t_i$ —— 奥林匹克竞赛的月份和日期（没有前导零）、所需的评审团成员数量以及准备第 $i$ 场奥林匹克竞赛所需的时间（$1\le m_i\le 12$，$d_i\ge 1$，$1\le p_i,t_i\le 100$），$d_i$ 不超过月份 $m_i$ 的天数。奥林匹克竞赛的给出顺序是任意的。几场奥林匹克竞赛可能在同一天举行。

在解题时使用现代（公历）日历。注意所有日期都是在2013年。这一年不是闰年，所以2月有28天。请注意，某些奥林匹克竞赛的准备工作可能会在2012年开始。

输出格式

输出一个整数 —— 评审团的最小人数。

输入输出样例 #1

输入 #1

2
5 23 1 2
3 13 2 3

输出 #1

2

输入输出样例 #2

输入 #2

3
12 9 2 1
12 8 1 3
12 8 2 2

输出 #2

3

输入输出样例 #3

输入 #3

1
1 10 1 13

输出 #3

1

题解

就是统计一下每一天需要多少人，用暴力求最大值就行了

Code

#include <bits/stdc++.h>

using namespace std;

int n;
int f[1000];
int a[20] = {0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};

int main()
{
//	freopen("10.in", "r", stdin);
//	freopen("10.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int a1, b, c, d;
		cin >> a1 >> b >> c >> d;
		d--;
		int l = a[a1] + b - d + 100;
		int r = a[a1] + b + 100;
		for (int j = l; j <= r; j++)
		{
			f[j] += c;
		}
	}
	int ans = 0;
	for (int i = 100; i <= 456; i++)
	{
		ans = max(ans, f[i]);
	}
	cout << ans << endl;
}