/ Vijos / 题库 /

天堂的馈赠

天堂的馈赠

背景

小杉找到了做棉花糖的最优方案,想去摘云朵,可是摔死了……
他来到了天堂。

天堂当然是很大的,也是很缭乱的。

小杉看到一块路标,写着“天堂的馈赠”。

描述

考虑到小杉刚死没多久,为了安抚他受创的心灵和思恋的感情,
天堂派出一个天使给小杉送礼,但IQ不够高的小杉可不能够拿到好礼物。

馈赠在天堂门口进行。天使站在云端,往下扔礼物。

天堂之门的宽度为W格(按1..W编号),高度为0格,云端的高度为H格,小杉只能站在格子里。

开始时(第0秒),小杉站在天堂之门的第P格。

馈赠开始后,天使会在某些时刻从云端的某格扔礼物下来,礼物下落的速度(格/秒)是不一样的。

小杉左右移动去接礼物(每秒可以移动1格或不移动)。

礼物之间的价值当然是不一样的,小杉事先知道了每个礼物的价值。

当礼物在某一秒末恰好到达小杉所在的格子中,小杉就接到了这个礼物。

小杉想知道,他最多可以拿到价值为多少的礼物。

而且,由于礼物下落的速度有些可以很……,小杉还想知道是不是有些礼物他怎么样也拿不到。

格式

输入格式

每组测试数据的
第一行有四个数W,P,H,N(1<=P<=W<=500),(1<=H<=500),(0<=N<=3000)
接下来N行,每行四个数t,r,v,s(0<=t<=1500),(1<=r<=W),(1<=v<=H),(|s|<=1e5)
表示天使在t时刻,云端的第r格,以v格/秒的速度扔下价值s的礼物
输入均为正整数
10%的数据W<=100,H<=100,N<=200

输出格式

对每组测试数据输出两行。

第一行仅有一个整数,表示小杉最多能拿到价值多少的礼物。

第二行也仅有一个整数,表示小杉不可能拿到的礼物总价值多少。

样例1

样例输入1

1 1 1 1
1 1 1 1

样例输出1

1
0

限制

每个测试点1s

提示

注意:当礼物在某一秒末 恰好 到达小杉所在的格子中,小杉才能接到这个礼物。

来源

lolanv

信息

ID
1235
难度
7
分类
动态规划 点击显示
标签
递交数
1193
已通过
226
通过率
19%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

天使的施舍 - CXF女儿满月邀请赛