DCP-107: Maximum Block Sum Back to All Problems

Hard Divide and Conquer > Dynamic Programming

You are playing a game with Alice. Before starting the game, Alice gives you a board with **N** rows and **M** columns. Each cell of the board ( there are N X M cells ) will have a number printed on it. Now Alice gives you P tile blocks, each tile block is **2 X 1** sized. You should put all the tile blocks on that given board. But your goal is to maximize the sum of those cell's number which are covered by the tile blocks. You started to think about the game and you found out that it will be quite hard to find the maximum sum if N and M is arbitrary number. As Alice is so kind, so she guarantees that M will always be 3 and permits you to rotate the tile blocks if you want. Input: ------ Input starts with an integer T (1<= T <= 10), denoting the number of test cases. each case contains the integer N (1 ≤ N ≤ 1000), the number of rows, and P (1 ≤ P ≤ 1000), the number of tile blocks will be given by Alice. Each of the following N lines contains three integers printed in the i'th row of the board. All numbers will be lesser than 10^9 by absolute value. Output: ------- For each case you should print the maximum sum achievable from that board if you put all the tile blocks efficiently. Sample Input ------------ 1 3 3 2 2 2 3 -3 -3 4 5 5 Sample Output ------------- 21 Hint ------------- You shouldn't cover the cells with negative value and one of the cell which have a value of 2

Problem Setter:

Ahmad Faiyaz

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 5.00
C++ 5.00
C++14 5.00
C# 10.00
Go 10.00
Java 10.00
JavaScript 10.00
Objective-C 10.00
Perl 10.00
PHP 10.00
Python 10.00
Python3 10.00
Ruby 10.00
VB.Net 10.00

Problem Stats




# User Language Timing
01 Morass Cpp14 0.73s
02 sahedsohel Cpp14 1.38s
03 dipta007 Cpp14 1.90s
04 mamun4122 Cpp14 2.16s
05 froghramar Cpp14 2.30s
06 feodorv C 2.37s
07 Robbinb1993 Cpp 3.42s
08 moinul_shaon Cpp14 3.48s

Your feedback is our precious!

Or call +88 02 9853138 for support