この問題も、前に解いた部分和を求める問題と似た方法で、部分和を求めるとタイムアウトしない問題です.NxN形式なので、数式を見つけるのは難しいです.

psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+arr[i][j]; これらの式を用いてpsumを求めた.

の結果値は、psum[x 2][y 2]−psum[x 1−1][y 2]−psum[x 2][y 1−1]+psum[x 1−1][y 1−1]のような式から求められる.

このようにしてもタイムアウトになるので、ジャンプラインは「n」を使います.

Code

#include <iostream>
#define MAX 1025
using namespace std;

int n, m;
int arr[MAX][MAX];
int psum[MAX][MAX];
int x1,y1,x2,y2;

void Input(){
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>arr[i][j];
            psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+arr[i][j];
        }
    }
}

int Solution(int x1, int y1, int x2, int y2){
    return psum[x2][y2]-psum[x1-1][y2]-psum[x2][y1-1]+psum[x1-1][y1-1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    for(int i=0; i<m; i++){
        cin>>x1>>y1>>x2>>y2;
        cout<<Solution(x1,y1,x2,y2)<<'\n';
    }
    return 0;
}