GlobeX Cup '18 S5 - Math Bash

View as PDF

Submit solution

Points: 17
Time limit: 0.6s
Java 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are taking your calculus exam. In the exam room, there is an N \times N grid of desks, each with exactly one student taking an exam at that desk.

Your teacher has came up with an interesting way of grading the exams. Let p_{i,j} represent the initial mark that the student at position (i,j) got on the exam. His actual mark, a_{i,j}, is equal to a_{i,j} = p_{i,j} + k_{i,j} where k_{i,j} is the number of students who have an actual mark higher than or equal to student (i,j)'s initial mark and their position is (x,y) where 1 \le x < i and 1 \le y < j. Formally, k_{i,j} is the number of students where a_{x,y} \ge p_{i,j} and 1 \le x < i, 1 \le y < j.

Wanting to know how much everyone's marks change, you are to find the sum of k_{i,j} for all i, j\ (1 \le i,j \le N).

Input Specification

The first line will contain the N\ (1 \le N \le 800).

The next line will contain N lines will each contain N space-separated integers p_{i,j}\ (1 \le p_{i,j} \le 10^9).

Output Specification

Output the sum of all k_{i,j}, as defined above.

Sample Input 1

2
2 1
1 2

Sample Output 1

1

Explanation for Sample 1

Only the student at position (2,2) will have their mark changed. All other students will keep their current mark. Thus, k_{1,1} = k_{1,2} = k_{2,1} = 0, and k_{2,2} = 1. The student at position (2,2) will have their marks changed by one due to a_{1,1} = 2\  (a_{1,1} \ge p_{2,2}). The sum of all k_{i,j} is therefore one.

Sample Input 2

5
1 4 2 5 3
5 2 8 4 2
1 1 1 1 3
9 9 2 3 1
1 1 1 1 1

Sample Output 2

82

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 5 4 3 2 1
10 9 8 7 6 1 2 3 4 5
10 9 8 7 6 1 2 3 4 5

Sample Output 3

1420

Comments

There are no comments at the moment.