I was asked an interesting problem on an university interview. (I won't tell you what university it was.) However, I couldn't come up with an effective solution. I would appreciate if anyone has any thoughts or approaches!

Statement

You are given two integers x y, and a n by n chessboard, each square is given either black, white, or red. (Denoted by 0,1,2) You also have an infinite amount of black, white, and red chess pieces. You are to put exactly one piece on each of the squares. You have to calculate the maximum score possible. The score is calculated as follows:

• For each square, if the color of the square is same as the color of the piece, you get x points.
• For each unordered pair of squares that are adjacent (up, down, left, right) if the color of the chess pieces are the same, you get y points.

Constraints

$$$n \le 100$$$ $$$x,y \le 10^9$$$

Sample Input

n=3 x=4 y=2
110
001
100

Sample Output

46

Explanation:

We can put the chess pieces as follows:

110
000
000

This way we have 7 chess pieces that have the same color as the square color, giving us 7x4=28 points. We also have 1 pair of white and 8 pairs of black pieces that are adjacent, giving us 9x2=18 points. Total is 46.

Link to problem : https://atcoder.jp/contests/abc233/tasks/abc233_h

I have read the editorial, and now I understand that we have to find the number of points that are inside a square area. We could use 2d prefix sums if the coordinates are small. However, the coordinates can be very large ($$$2\times 10^5\times 2 \times 10^5$$$), and that will lead to MLE.

Also, I have read some submissions, and most of them use one of the following solutions:

1. Binary indexed tree (Fenwick Tree) + offline queries

2. Some sort of segment tree -ish thing + online queries

I would really appreciate if someone could kindly explain a solution^_^

I just recieved a message saying that my solution in the last div.3 contest coincided with someone else's. I'm mistakenly accused of cheating in #719 (Div. 3)

Attention!

Your solution 115267864 for the problem 1520C - Not Adjacent Matrix significantly coincides with solutions Chaturved/115261480, EasonCookie197/115267864, natasha_25/115272375. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I swear that I didn't cheat in the contest, and all the codes in this contest are 100% written by me. I didn't use an online IDE. I don't know the other two users. The coincidence is caused by a trivial approach to the problem : just print all the odd numbers and then all the even numbers in order. I believe many other contestants used the exact same method too,with very similar codes. I hope I can get my ratings back. Can someone help me please...