2xN Pretty Tiling
Time limit2sMemory limit512 MB
Tile a 2xN grid with at most A dominoes and at most B 2x2 squares, rotating tiles freely, to maximize the sum of tile prettiness values.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Greedy, Sorting, Implementation
- Solved
- No attempts yet
Problem
In 2021, water kept overflowing in the restroom of the College of Informatics, to the point that the floor tiling had to be redone. Minkyu, a master of tiling, has lived by the motto "tiling should always be pretty." The restroom floor that needs new tiling is represented as a 2×N grid. Minkyu has A tiles of size 2×1 and B tiles of size 2×2. Each tile has a degree of "prettiness," and the prettiness of the restroom floor is the sum of the prettiness of the tiles that make up the floor. Minkyu wants to tile the restroom floor using the tiles he has so that the floor's prettiness is maximized. What is the maximum prettiness he can obtain?
This is a case that achieves the maximum prettiness of sample 1. Tiles can be rotated 90 degrees.
Input
The first line gives the integers N, A, and B (1 ≤ N, A, B ≤ 2000, 2 × B + A ≥ N), separated by spaces.
The second line gives A integers, separated by spaces, each the prettiness of a 2×1 tile.
The third line gives B integers, separated by spaces, each the prettiness of a 2×2 tile.
The prettiness of each tile is a positive integer not greater than 1,000,000.
Output
Print the maximum prettiness of the restroom floor that Minkyu can obtain using the tiles he has.