#PU1017. USACO 2020 February Contest, Gold — Problem 1. Timeline
USACO 2020 February Contest, Gold — Problem 1. Timeline
USACO 2020 February Contest, Gold — Problem 1. Timeline
题目描述
Bessie attended milking sessions () over the past days
(). However, she is having trouble remembering when she
attended each session.
For each session , she knows that it occurred no earlier than
day (). Additionally, Bessie has memories
(), each described by a triple , where she recalls that
session happened at least days after .
Help Bessie by computing the earliest possible date of occurrence for each
milking session. It is guaranteed that Bessie did not remember incorrectly;
in other words, there exists an assignment of sessions to days in the range
such that all constraints from her memories are satisfied.
输入格式
The first line of input contains , , and .
The next line contains space-separated integers . Each
is in the range .
The next lines contain three integers, , , and indicating that
session happened at least days after . For each line, ,
and are in the range , and is in the range .
输出格式
(见题面原文)
数据范围
Test cases 2-4 satisfy .
Test cases 5-10 satisfy no additional constraints.
样例
样例 1
4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4
1
6
3
8
Session two occurred at least five days after session one, so it cannot have
occurred before day $1+5=6.$ Session four occurred at least two days after session
two, so it cannot have occurred before day $6+2=8$.
Problem credits: Mark Gordon