← 返回题目列表

Codeforces · 1267/A

A. 学徒学习轨迹

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Apprentice Learning Trajectory - 原题 PDF 第 1 页
原题PDF第1页
可复制的 PDF 提取文本
ICPC 2019–2020, NERC – Northern Eurasia Finals
                         St. Petersburg, Barnaul, Tbilisi, and Almaty, December 1, 2019
Problem A. Apprentice Learning Trajectory

    Time limit:     3 seconds

Abigail is an apprentice studying to become a blacksmith. She wants to plan her learning trajectory and
make as many swords as possible on her way to becoming a famous expert.

There are n masters willing to host her as their apprentice. The i-th master will start working at the
minute ai and end working at the minute bi, working for a total of bi −ai minutes. During this interval
of time, Abigail can work at this master’s forge. She can enter and leave the forge several times and
produce one or several swords upon each arrival. However, in order to produce a sword under supervision
of the i-th master she has to work there for ti minutes in a row. She can’t leave the sword unfinished and
continue working on it upon her next arrival to this forge.

Help Abigail make an optimal plan and calculate the maximum number of swords she can produce under
the supervision of n masters.

Input

The first line contains integer n (1 ≤n ≤200 000) — the number of masters.
Each of the next n lines contains three integers ai, bi, ti (1 ≤ai < ai + ti ≤bi ≤1018) — the start and the
end time of master’s work, and the time needed to make one sword in their forge.

Output

Output the maximum number of swords Abigail can produce using the optimal learning trajectory.

Examples

   standard input     standard output                   Illustration
 2                   5
 5 7 1                                                2
 1 9 2                                                                     1


                                                            0     1     2     3     4     5     6     7     8     9    10

 3                   4
 1 10 4                                                                           3
                                                                         2 6 12 3
                                                      1
 9 13 2
                                                           0   1   2   3   4   5   6   7   8   9   10  11  12  13  14

 3                   4
 1 13 4                                                                           3
                                                                         2 6 11 2
                                                      1
 9 13 3
                                                           0   1   2   3   4   5   6   7   8   9   10  11  12  13  14





                                         Page 1 of 15