2215 Parliament
問題概要
R行S列の行列が与えられる。
この行列のR1行S1列からR2行S2列までの長方形の部分の成分の和を求めよ。
行列の各成分はintに収まる範囲であり、R,S≦1000を満たす。
解法
i行j列目までの和をs[i][j]などとして持っておけば、
長方形の和はO(1)で計算できる。
ソースコード
int w,h,a[1000][1000]; ll s[1001][1001]; int main(){ int T; scanf("%d",&T); rep(U,T){ scanf("%d%d",&h,&w); rep(i,h)rep(j,w){ scanf("%d",a[i]+j); s[i+1][j+1]=a[i][j]+s[i+1][j]+s[i][j+1]-s[i][j]; } int q,x1,x2,y1,y2; scanf("%d",&q); rep(i,q){ scanf("%d%d%d%d",&y1,&x1,&y2,&x2); x1--; y1--; ll ans=s[y2][x2]+s[y1][x1]-s[y2][x1]-s[y1][x2]; printf("Absolutni hodnota pohodlnosti je %lld bodu.\n",ans); } puts(""); } return 0; }