time limit per test: 0.25 sec. memory limit per test: 4096 KB
input: standard input output: standard output
There is a half-waterlogged underwater station not far from the famous country Berland. The station consists of N levels. The following information is known about each level: Wi - the weigth of water on i-th before the act of terrorism, Li - the weight of water the i-th level can hold, and Pi - amount of money terrorist are required to depressurize i-th level. All the water from the depressurized level pours to the next level. If the weight of the water on i-th level is more then Li, then it becomes depressurized. The terrorists from Pivland want to depressurize the last (N-th) level spending the least amount of money. They hired you to do this.
The first line of input contains the natural number N (1<=N<=15000). Each of the following N lines contains 3 numbers Wi, Li, Pi (0<=Wi,Li,Pi<=15000).
Write to the output the numbers of levels, which must be depressurized.
3 1000 1000 1 0 1000 2 2 10 100
Andrew V. Lazarev
Saratov Regional Olympiad, 2002
Codeforces (c) Copyright 2010-2019 Mike Mirzayanov