DMOPC '21 Contest 3 P6 - Good Grids

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 1.5s
Memory limit: 256M

Problem types

An N by M grid of characters is called good if it satisfies these three conditions:

  • Each character is either A, B, or C.
  • Every 2 by 2 subgrid contains all three different letters.
  • Any two cells that share exactly one corner contain different letters.

Let (x,y) denote the cell in the x-th row from the top and y-th column from the left.

You want to construct a good grid that satisfies some of K constraints. Each constraint consists of a positive integer value a_i and two cells (x_{i1},y_{i1}) and (x_{i2},y_{i2}) that share an edge. You will get a_i points if your good grid has the same letter in cells (x_{i1},y_{i1}) and (x_{i2},y_{i2}).

Find a good grid that gets the most total number of points.


2 \le N, M \le 50

0 \le K \le 5000

For all i:

  • 1 \le a_i \le 10^9
  • 1 \le x_{i1}, x_{i2} \le N
  • 1 \le y_{i1}, y_{i2} \le M
  • |x_{i1}-x_{i2}|+|y_{i1}-y_{i2}| = 1

Input Specification

The first line contains three space-separated integers: N, M, and K.

The next K lines contain five space-separated integers: a_i, x_{i1}, y_{i1}, x_{i2}, and y_{i2}.

Output Specification

On the first line, output the maximum total number of points obtainable by a good grid.

On the next N lines, output a good grid that obtains this total number of points. If there are many possible good grids, output any of them.


For each test case:

  • You will receive 100\% of the points if your first line of output contains the correct answer and the remaining lines contain a correctly formatted good grid that obtains this total number of points.
  • Otherwise, you will receive 80\% of the points if your first line of output contains the correct answer. You do not need to print anything after the first line if you are aiming for these partial points, as long as you ensure that the first line is terminated by a \n character. You will still receive these partial points if you output a malformatted or incorrect grid.
  • Otherwise, you will receive 0 points.

Your final score is the minimum score over all test cases.

Sample Input

3 4 6
3 1 2 1 3
1 2 3 1 3
4 3 4 2 4
1 2 2 3 2
5 2 1 2 2
9 2 1 2 2

Sample Output



This grid is good and satisfies the 1st, 3rd, 5th, and 6th constraints, for a total of 3+4+5+9 = 21 points. It can be proven that it is impossible to obtain more than 21 points.


There are no comments at the moment.