| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14016 | OSHINOKODA |
|
| 14422 | A perfect bed for Shiro |
|
Description
Ai is a super idol with the perfect smile.
All of her fans said that there was a star in her eye.
One day, a piece of shocking news claimed that she had become the mother of twins!
To prove this news, an easy way is to find if there is also a star in the baby's eye.
Also, because Ai's children must have the brightest star in their eyes, we need a program to automatically calculate the brightness of a star with a given picture.
Given an image (square matrix) A[N,N], if point P(X,Y) is the center of a star, the brightness is the summation of:
(1) A[X][j], for all 0<=j<N (The values in the Xth row)
(2) A[i][Y], for all 0<=i<N (The values in the Yth column)
(3)
A[X+i][Y+i], for all -N<=i<N if 0<=(X+i)<N and 0<=(Y+i)<N
A[X+i][Y-i], for all -N<=i<N if 0<=(X+i)<N and 0<=(Y-i)<N
(The values of two diagonals from the centers)
Note that when calculating the brightness, the value of the center points is calculated only once.
Please help her fans find the truth, or they may become very angry @@.
Hint.
If you cannot pass all the testcases, you can try to use extra arrays to record some information when you read the input data.
By doing so, you can immediately determine whether a point is a star.
Input
In this problem, with a given image (square matrix), you have to solve T solutions.
There are four parts of the input:
(1) The number of testcases, T. 1<=T<=200000
(2) The size of the square matrix, N. 1<=N<=1024
(3) An N*N matrix separated by a newline character. 0<=The values in the matrices<=N.
(4) T pairs of center points composed of 2 integers, representing the position of the center points.
Output
The brightness of each star in the matrix.
It is guaranteed that the brightness can be represented using unsigned long long datatype.
Note that you need to print "\n" in the end of each answer.
Sample Input Download
Sample Output Download
Discuss
Description
I don't have any pictures of Domo, so here is my cat. His name is Shiro
He sleep on my book to prevent me from studying, what a nice cat
You wan't to find the perfect bed for Shiro, so that he will not sleep on my book again
Given array A, the perfect bed is determined by the highest sum value from subarray between index i and j,
For example given array below:
The highest value is 7, which from index 2 to 6, as the sum is 4 + (-1) + (-2) + 1 + 5 = 7
Let S be an array of prefix sum A
then S[i] = A[0] + A[1] + A[2] + ... + A[i]
e.g. prefix sum of the above array will be:
[-2, -5, -1, -2, -4, -3, 2, -1]
and try to find the relation between the subarray
Input
There are T test cases
each test case has an integer N on the first line and then followed by N integers in the next line: a0, a1, a2, ..., aN-1
1 <= T <= 100
1 <= N <= 50000
-109 <= ai <= 109
Output
For each testcase, print the maximum points of subarray, following by newline character