시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 2 | 1 | 1 | 50.000% |
A railway company just launched a new train prototype made out of a single railway wagon containing N chairs. Each chair is labelled from 1 to N (starting at the front of the train) and they are arranged in a row, one behind the other. The following rules must be followed by every passenger:
Train route contains M stations, each labelled from 1 to M. The train will stop at each station, starting with station 1 and ending with station M. Across all M train platforms, there are a total of N passengers, labelled from 1 to N. The ticket price, as well as the boarding and destination stations are known in advance for each passenger.
The railway company wants to have only happy customers that reach their destination. In order to have only happy customers, the company allowed the conductor to choose which passengers can board and in which order they are allowed to do it. So, the conductor can choose to not allow certain passengers to board.
Find out what is the largest profit that the company can make having only happy customers, and also one valid ordering of embarkment that would yield this profit.
The standard input contains the following input:
Within each line, the numbers are positive integers and are separated by exactly one space.
The standard output should have the following format:
번호 | 배점 | 제한 |
---|---|---|
1 | 10 | N ≤ 25 |
2 | 30 | 26 ≤ N ≤ 2500 |
3 | 60 | 2501 ≤ N ≤ 100000 |
4 8 2 6 10 4 5 1 3 7 10 1 7 10
20 2 1 3
A correct answer can be obtained as such:
4 10 1 3 3 1 10 2 2 5 3 1 2 5
11 3 4 1 3
A correct answer can be obtained as such: