All Tracks Algorithms Graphs Min-cut Problem

Covering Chessboard
Tag(s):

Medium-Hard

Problem
Editorial
Analytics

You have an n by m grid. Each grid square has a certain value associated with it. This is given by the numbers vi,j.

You can capture grid squares in two different ways.

  1. You can directly capture a grid square. This costs ci,j.
  2. You can indirectly capture a grid square. You can only do this if we have already captured all of this squares neighbors. This costs bi,jci,j.
Two squares are neighbors if they share an edge.

Your score is the sum of values you have captured minus the cost it took to capture those squares. Return the maximum possible score you can achieve.

Input format:

The first line of input will contain two integers n, m.

The next n lines of input will contain m space separated integers each. The j-th number on the i-th line denotes vi,j.

The next n lines of input will contain m space separated integers each. The j-th number on the i-th line denotes bi,j.

The next n lines of input will contain m space separated integers each. The j-th number on the i-th line denotes ci,j.

Output format:

Print a single integer, the answer to the problem.

Constraints

For all subtasks:
0 ≤ vi,j ≤ 100,000
0 ≤ bi,jci,j ≤ 100,000
1 ≤ n, m

Subtask 1 (45 pts):
n, m ≤ 3

Subtask 2 (35 pts):
n, m ≤ 7

Subtask 3 (20 pts):
n, m ≤ 25

SAMPLE INPUT
3 5
9 0 3 2 4
0 2 8 6 2
5 3 4 1 3
5 1 7 9 5
2 4 1 2 4
9 1 2 2 0
9 1 8 9 7
2 7 3 2 9
9 1 9 8 2
SAMPLE OUTPUT
13
Explanation

A more human-readable version of the input is as follows:

3 5
9 0 3 2 4
0 2 8 6 2
5 3 4 1 3

5 1 7 9 5 2 4 1 2 4 9 1 2 2 0

9 1 8 9 7 2 7 3 2 9 9 1 9 8 2

The optimal strategy in this case is to directly capture the following squares:

O X O O O
X O X X O
O X O O X
And indirectly capture only the top left square.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications