锻炼计划 (exercise. c/cpp/pas)
背景
身体是革命的本钱, OIers 不要因为紧张的学习和整天在电脑前而忽视了健康问题. 小 x 设计了自己的锻炼计划, 但他不知道这个计划是否可行, 换句话说如果计划不当可能会让他的体力超支, 所以小 x 请你帮助他. 一天有 1440 分钟, 所以小 x 列出的是这一整天第 1 至第 1440 分钟的计划. 小 x 的体力用一个整数来表示, 他会按照计划表进行锻炼, 同时, 每分钟小 x 的体力会自动增加 1. 如果某一分钟末小 x 的体力小于等于零, 那么可怜的小 x 就累死了……
输入 (exercise. in)
第一行是用空格分开的两个整数 n, m, 分别表示小 x 的初始体力值和计划的项目数量. 从第二行开始的 m 行, 每行描述一个锻炼项目: 名称、开始时间 a、结束时间 b、每分钟耗费的体力 (用空格分隔), 表示此项目从第 a 分钟初开始, 第 b 分钟末结束. 锻炼项目按照开始时间递增顺序给出, 不会出现两个项目时间冲突的情况.
输出 (exercise. out)
输出包括两行, 如果计划可行, 第一行输出 “Accepted”, 第二行输出这一天过后最后剩余的体力; 否则在第一行输出 “Runtime Error”, 第二行输出在第几分钟累死.
样例输入
10 1
Basketball样例输出
Accepted
1440约定
\(0 \lt n \leq 2^{31} - 1\)
\(0 \leq m \leq 500\)
所有中间值的绝对值不会超过\(2^{31} - 1\) 每一个锻炼项目的名称不超过 20 个字符, 其中不含空格.
Explanation
水题...... 可以用线段树, 但是似乎 \(O(n^2)\) 能过~
Example Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef long long lli;
const int maxn = 1600;
lli day[maxn];
int m;
int main(int argc, char** argv)
{
scanf("%lld%d", &day[0], &m);
for (int i = 1; i <= m; i++) {
lli a = 0;
int b = 0, c = 0;
char str[40];
scanf("%s%d%d%lld", str, &b, &c, &a);
for (int j = b; j <= c; j++)
day[j] += a;
}
int fail = 0;
for (int i = 1; i <= 1440; i++) {
day[i] = day[i - 1] - day[i] + 1;
if (day[i] <= 0) {
fail = i;
break;
}
}
if (!fail) {
printf("Accepted\n%lld\n", day[1440]);
} else {
printf("Runtime Error\n%d\n", fail);
}
return 0;
}