#PU1520. USACO 2025 US Open Contest, Silver — Problem 3. Ski Slope
USACO 2025 US Open Contest, Silver — Problem 3. Ski Slope
USACO 2025 US Open Contest, Silver — Problem 3. Ski Slope
题目描述
Bessie is going on a ski trip with her friends. The mountain has waypoints () labeled in increasing order of altitude (waypoint is the bottom of the mountain). For each waypoint , there is a ski run starting from waypoint and ending at waypoint (). This run has difficulty () and enjoyment (). Each of Bessie's friends () will do the following: They will pick some initial waypoint to start at, and then follow the runs downward (to , then to , and so forth) until they get to waypoint . The enjoyment each friend gets is equal to the sum of the enjoyments of the runs they follow. Each friend also has a different skill level () and courage level (), which limits them to selecting an initial waypoint that results in them taking at most runs with difficulty greater than . For each friend, compute the maximum enjoyment they can get.
输入格式
The first line contains . Then for each from to , a line follows containing three space-separated integers , , and . The next line contains . The next lines each contain two space-separated integers and .
输出格式
(见题面原文)
数据范围
Inputs 2-4: Inputs 5-7: All Inputs 8-17: No additional constraints. Problem credits: Brandon Wang
样例
样例 1
4
1 20 200
2 30 300
2 10 100
8
19 0
19 1
19 2
20 0
20 1
20 2
29 0
30 0
0
300
500
300
500
500
300
500
The first friend cannot start any waypoint other than $1$, since any other
waypoint would cause them to take at least one run with difficulty greater than
$19$. Their total enjoyment is $0$.
The second friend can start at waypoint $4$ and take runs down to waypoint
$2$ and then $1$. Their total enjoyment is $100+200=300$. They take one run with
difficulty greater than $19$.
The third friend can start at waypoint $3$ and take runs down to waypoint
$2$ and then $1$. Their total enjoyment is $300+200=500$. They take two runs with
difficulty greater than
$19$.
提示
use of 64-bit integer data types (e.g., a "long long" in C/C++).