[백준] 30461번 낚시 (gold 4

import java.io.*;
import java.util.*;

public class Main{
    static int[][] map;
    static int n;
    static int m;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        n=Integer.valueOf(st.nextToken());
        m=Integer.valueOf(st.nextToken());
        int q=Integer.valueOf(st.nextToken());

        map=new int[n+1][m+1];
        for(int i=1; i<=n; i++){
            st=new StringTokenizer(br.readLine());
            for(int j=1; j<=m; j++){
                map[i][j]=Integer.valueOf(st.nextToken());
            }
        }

        //누적합. a,b에 미끼를 던지면 위로 쫙 걸리므로.
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                map[j][i]+=map[j-1][i];
            }
        }

        //대각선으로 dp 대각선으로 움직이면서 끌고오므로.
        //이때 누적합으로 더한 값들이 있어서 걍 대각선으로 더하기만 하면됨.
        //이렇게하면 dp발생안되는 구간이 발생함.
        //y축으로도 진행
        for(int i=1; i<=m; i++){
            dp(1,i);
        }
        for(int i=2; i<=n; i++){
            dp(i,1);
        }

        StringBuilder sb=new StringBuilder("");
        for(int i=0; i<q; i++){
            st=new StringTokenizer(br.readLine());
            int y=Integer.valueOf(st.nextToken());
            int x=Integer.valueOf(st.nextToken());
            sb.append(map[y][x]+"\n");
        }
        System.out.print(sb.toString());
    }

    public static void dp(int ty , int tx){
        while(true){
            tx+=1;
            ty+=1;
            if(ty>n ||tx>m){
                break;
            }
            map[ty][tx]+=map[ty-1][tx-1];
        }
    }
}