yes

C. Matrix Game

Time Limit: 6 seconds

Memory Limit: 1024 MB

Rating: 1600

Charlie has an $N \cdot N$ matrix of integers. He plays a game involving this matrix with Gareth. Each player takes turns, with both players’ scores being $0$ at the start. Charlie goes first. When it’s his turn, Charlie removes a row of integers from the matrix and adds the sum of all the integers in that row to his score. When it becomes his turn, Gareth removes a column of integers from the matrix and adds the sum of all the integers in that column to his score. After all elements in the matrix has been removed, who has the higher score in the end? Output ‘C’ if Charlie has a higher score, ‘G’ if Gareth does and ‘D’ if it’s a draw. (without quotes). Assume both players play optimally. $1 \le N \le 1{,}000$

The first line has integer $N$, followed by $N$ lines containing information about the starting matrix.

Output the answer.

Sample Input 1:
1 0
2 -3

Sample Output 1:
G

Sample Input 2:
5
1 2 3 4 5
6 7 8 9 10
-1 -2 -3 -4 -5
-6 -7 -8 -9 -10
0 0 0 0 0

Sample Output 2:
F

Sample Input 3:
1
0

Sample Output 3:
D

For the first test case, let's assume Frank removes the first row. Then Gareth's optimal move has to be the first column, as it has a $2$, rather than $-3$. Now Frank is forced to take $-3$ on his turn, resulting in Gareth's victory, as $-2 < 2$. Let's see what happens when Frank removes the second row. Frank adds $-1$ to his score, and Gareth adds $1$ to his score. Frank adds $0$ to his score. Gareth still wins, as $-1 < 1$. Therefore, Gareth wins with this starting configuration.

IanOJ Contest #3 (Div. 2) > Problem C