All submissions for this problem are available.
Jason and his dad own an apple orchard of size N x M. And every fall he would help his father pick apples for the production of cider. But the cider press can take only K kilograms a day due to its small size. Every day he would pick apples only in a special sub-rectangle which has size S x T where S<=X and T<=Y, for some fixed X and Y. He has Q queries, each query contains X, Y. For each query, he wanted to know how many special sub-rectangles contain at least K kilograms of apples..
The first line of the input contains integers N, M and K(1<=N, M<=300, 1<=K<=N*M).
The next N lines contain M characters (either 'A' or '.'). 'A' means there is 1 kg of apples in that cell, while '.' means there are no apples in that cell.
The next line contains an integer Q (1<=Q<=100 000).
The next Q lines contain integers X and Y (1<=X<=N , 1<=Y<=M).
The output contains Q lines, each line contains the number of special sub-rectangles which satisfy the requirement. (The amount of apples is at least K inside the special sub-rectangle)
Input: 5 5 4 A.A.. ..A.. A...A AAAA. AA..A 2 1 1 2 3 Output: 0 4
Note : The reference for this problem has been taken from : Codechef
|Time Limit:||0.169811 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.