Making the Best Team
InterviewTime limit1sMemory limit128 MB
Choose 15 players for white and 15 for black from a list of up to 1000 players to maximize the total ability sum.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Greedy, Array
- Solved
- No attempts yet
Problem
Each year, the Kkung Association forms a 30-player team for a world chess competition. The team must have 15 players assigned to white and 15 players assigned to black. For every player, their white ability and black ability are given as integers from 1 to 100. A player can participate in only one color during the competition, and some players may be left out. The team's total ability is the sum of the white abilities of the players assigned to white plus the black abilities of the players assigned to black. Find the maximum possible total ability.
Input
The input consists of player ability values. Each line contains two integers W and B separated by a space. W is the player's ability when playing white, and B is the player's ability when playing black. The input has at least 30 lines and at most 1000 lines, and should be read until end of file.
Output
Print the maximum total ability among all teams that can be formed.