days days in a country (days are numbered from zero). The country has cities cities, each directly reachable from every other. The trip may start in any city.
The table stay may cover more days than the trip lasts; any extra rows are simply unused.
Each day the traveller picks one option:
- stay in the current city c and earn stay[d][c] points, where d is the day number;
- move from the current city c to another city t and earn travel[c][t] points.
Return the highest total the whole trip can earn.cities=2, days=2, stay=[[1, 5], [4, 2]], travel=[[0, 3], [6, 0]] → 11
Start in city 1 and stay there on day 0 (+5), then move to city 0 on day 1 (+6). Total 11.
cities=3, days=1, stay=[[2, 7, 1]], travel=[[0, 9, 0], [0, 0, 0], [0, 0, 0]] → 9
With a single day, moving from city 0 to city 1 earns 9, more than staying anywhere.
cities=1, days=3, stay=[[4], [1], [3]], travel=[[0]] → 8
cities ≤ 200days ≤ 200days ≤ len(stay) ≤ 200, len(stay[d]) = citiestravel is a cities × cities matrixstay[d][c] ≤ 100travel[c][t] ≤ 100travel[c][c] = 0cities=2, days=2, stay=[[1, 5], [4, 2]], travel=[[0, 3], [6, 0]]
11
Run checks the first 3 tests in your browser. Submit checks all 47 tests on the server, hidden ones included.