Theater shade in Berland
All submissions for this problem are available.
In Berland a new movie was released on the occassion of 14th Feb. The craze for this movie was very much among the peoples of the city. So many of them decided to go to the only Movie Theatre of Berland. As berland is very much developed there are many large(tall) buildings, including the movie theatre. At each building except theatre, there exist a person (who wants to see movie) or a taxi driver with his taxi. As it is very late in the night each taxi driver will only accomodate only one passenger and also he will only drive for T[i] HRS (return journey is not included). You will be given the distance between building D[i] and the speed of each taxi driver S[i]. As I am the owner of this theatre help me by telling, the maximum number of people I will see in the theatre for the movie. N+P+1th building is the my theatre.
- First line contains TT the number of test cases.
- First line of each test test case contains N, P and R denoting the number of taxi, number of people, and the number of roads between buildings.
- Next line contains N space-seperated integers representing the building where taxi is present.
- Next line contains P space-seperated integers representing the building where passengers is present.
- Next R lines contains X, Y, and D[i] the building connected via road and the distance between them in KMs.
- Next line contains N space-sperated integers S[i] giving the speed details of each taxi in KM/HRs.
- Next line contains N space-sperated integers T[i] giving the time details of each taxi in HRs.
- Maximum number of people that will visit my theatre.
Constraints and Subtasks
- 1 <= TT <= 5
- 1 <= N <= 500
- 1 <= P <= 1000
- 1 <= R <= 50000
- 1 <= X, Y <= N
- 5 <= S[i] <= 50
- 1 <= T[i] <= 5
- 1 <= D[i] <= 100
Subtask 1: 20 points
- TT = 1
- 1 <= N <= 10
- 1 <= P <= 100
- 1 <= R <= 1000
Subtask 2: 20 points
- TT = 1
- 1 <= N <= 100
- 1 <= P <= 500
- 1 <= R <= 10000
Subtask 3: 60 points
- original constraints.
Input: 1 1 2 4 2 1 3 1 2 5 2 3 5 3 4 10 1 3 8 20 1 Output: 1
|Tags||adi28galaxyak, cdva16, dijkstra, matching, maxflow, medium-hard|
|Time Limit:||1 - 3.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.