Car Race Maintenance
Time limit1sMemory limit128 MB
Given a maximum travel range and per-station maintenance times, select a minimum-cost subset of stations so consecutive gaps never exceed the range, and output the chosen stations.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Greedy, Prefix sum
- Solved
- No attempts yet
Problem
A nationwide car race is held every year. The distance from the starting point to the finish line is very long, so each car may receive maintenance at repair stations along the road. The stations are numbered in order from the start toward the finish, beginning with 1.
By the race rules, after receiving maintenance, a car cannot travel farther than a fixed maximum distance before its next maintenance stop. Each repair station may require a different amount of maintenance time.
Choose the repair stations to visit while traveling from the start to the finish under this rule so that the total maintenance time is minimized. Write a program that outputs the minimum total maintenance time and the stations to visit.
For instance, suppose there are 5 repair stations and a car can travel at most 140 km after one maintenance. The distance from the start to station 1 is 100 km, and station 1 takes 5 minutes. Visiting stations 1, 3, and 5 takes 16 minutes in total, while visiting stations 2 and 4 takes 21 minutes, so the first route is better.
Input
The first line contains the maximum distance the car can travel without maintenance.
The second line contains the number n of repair stations. There are at most 100 stations.
The third line contains the distances of adjacent road segments from the start, through the stations, to the finish. Therefore, n + 1 distances are given. Each distance is at most the maximum distance, and the sum of all distances is at most 2^31 - 1.
The fourth line contains the maintenance times for stations 1 through n, in order. The sum of all maintenance times is at most 2^31 - 1.
All input values are positive integers not exceeding 2^31 - 1.
Output
On the first line, output the minimum total maintenance time spent at repair stations.
On the second line, output the number of repair stations visited.
If at least one station is visited, output their station numbers on the third line in travel order, separated by single spaces.
If no station needs to be visited, the total maintenance time is 0 and the station-number line is omitted.