r 行 c 列の格子のマスごとに整数が一つずつ書かれている。
一番上の行が 1 行目、一番左の列が 1 列目である。
質問が q 個与えられ、各質問は四つの数 r₁ c₁ r₂ c₂ で「行 r₁〜r₂、列 c₁〜c₂（両端を含む）からなる長方形の中の数をすべて足した値」を問う。
質問ごとに答えを一行ずつ、与えられた順に出力せよ。
一行目に r、c、q、続く r 行に各行の数 c 個、続く q 行に質問が空白区切りで与えられる。
3 4 3 1 2 3 4 5 6 7 8 9 10 11 12 1 1 3 4 2 2 3 3 1 4 3 4
78 34 24
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
質問ごとにマスを足し直すと最大 1 万質問 × 1 万マス = 1 億回です。
Python は時間内に終わらず、Craykon は実行ステップ上限（約 5 千万）を超えて止まります。
二次元累積和 P[i][j] =「(1,1) から (i,j) までの長方形の和」を P[i][j] = a[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1] で一度作れば（0 行目・0 列目は 0）、答えは P[r₂][c₂] - P[r₁-1][c₂] - P[r₂][c₁-1] + P[r₁-1][c₁-1] ですぐ出ます。
罠は三つ：r₁-1、c₁-1 の代わりに r₁、c₁ で引くと一番上の行と一番左の列が抜けます。
二回引いた左上の部分を足し戻すのを忘れがちです。
そして和は最大 10⁴ × 10⁶ = 10¹⁰ なので、C・C++・Java・C# で int（約 21 億）に入れるとあふれます — long/long long を使います。
Python は整数の大きさに限りがなく、JavaScript・TypeScript・Craykon は 2^53 まで正確なので大丈夫です。
二次元配列の作り方は言語ごとに違います：Python [[0] * (c + 1) for _ in range(r + 1)]（[[0] * (c + 1)] * (r + 1) は同じ行を何度も指すので誤り）、JS Array.from({ length: r + 1 }, () => new Array(c + 1).fill(0))、Java new long[r + 1][c + 1]（0 で埋まる）、C# 矩形配列 new long[r + 1, c + 1] と P[i, j]、C グローバルの long long P[101][101]、C++ vector<vector<long long>>。
Craykon は行ごとに 新リスト(c + 1, 0) を P.追加(…) で積みます — 一行は 101 マスなのでリスト上限（10,000 個）の心配はありません。
import sys data = sys.stdin.buffer.read().split()r, c, q = int(data[0]), int(data[1]), int(data[2])pos = 3 # P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다P = [[0] * (c + 1) for _ in range(r + 1)]for i in range(1, r + 1): for j in range(1, c + 1): P[i][j] = int(data[pos]) + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] pos += 1 out = []for _ in range(q): r1, c1, r2, c2 = map(int, data[pos:pos + 4]) pos += 4 out.append(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1])print("\n".join(map(str, out)))const t = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [r, c, q] = t;let pos = 3; // P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다const P = Array.from({ length: r + 1 }, () => new Array(c + 1).fill(0));for (let i = 1; i <= r; i++) { for (let j = 1; j <= c; j++) { P[i][j] = t[pos++] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]; }} const out = [];for (let k = 0; k < q; k++) { const [r1, c1, r2, c2] = t.slice(pos, pos + 4); pos += 4; out.push(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]);}console.log(out.join("\n"));import { readFileSync } from "node:fs";const t: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [r, c, q] = t;let pos = 3; // P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다const P: number[][] = Array.from({ length: r + 1 }, () => new Array(c + 1).fill(0));for (let i = 1; i <= r; i++) { for (let j = 1; j <= c; j++) { P[i][j] = t[pos++] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]; }} const out: number[] = [];for (let k = 0; k < q; k++) { const [r1, c1, r2, c2] = t.slice(pos, pos + 4); pos += 4; out.push(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]);}console.log(out.join("\n"));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int r = Integer.parseInt(st.nextToken()), c = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken()); // P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0(자바 배열은 0으로 채워진다) long[][] P = new long[r + 1][c + 1]; for (int i = 1; i <= r; i++) { st = new StringTokenizer(br.readLine()); for (int j = 1; j <= c; j++) { P[i][j] = Long.parseLong(st.nextToken()) + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]; } } StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(br.readLine()); int r1 = Integer.parseInt(st.nextToken()), c1 = Integer.parseInt(st.nextToken()); int r2 = Integer.parseInt(st.nextToken()), c2 = Integer.parseInt(st.nextToken()); out.append(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]).append('\n'); } System.out.print(out); }}using System;using System.Text; class Program{ static void Main() { string[] t = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int r = int.Parse(t[0]), c = int.Parse(t[1]), q = int.Parse(t[2]); int pos = 3; // P[i, j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0 long[,] P = new long[r + 1, c + 1]; for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++) P[i, j] = long.Parse(t[pos++]) + P[i - 1, j] + P[i, j - 1] - P[i - 1, j - 1]; var sb = new StringBuilder(); for (int k = 0; k < q; k++, pos += 4) { int r1 = int.Parse(t[pos]), c1 = int.Parse(t[pos + 1]), r2 = int.Parse(t[pos + 2]), c2 = int.Parse(t[pos + 3]); sb.Append(P[r2, c2] - P[r1 - 1, c2] - P[r2, c1 - 1] + P[r1 - 1, c1 - 1]).Append('\n'); } Console.Write(sb); }}#include <iostream>#include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int r, c, q; std::cin >> r >> c >> q; // P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다 std::vector<std::vector<long long>> P(r + 1, std::vector<long long>(c + 1, 0)); for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) { long long v; std::cin >> v; P[i][j] = v + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]; } } for (int k = 0; k < q; k++) { int r1, c1, r2, c2; std::cin >> r1 >> c1 >> r2 >> c2; std::cout << P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1] << '\n'; }}#include <stdio.h> #define MAX 100 /* P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0(전역 배열은 0으로 시작) */static long long P[MAX + 1][MAX + 1]; int main(void) { int r, c, q; scanf("%d %d %d", &r, &c, &q); for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) { long long v; scanf("%lld", &v); P[i][j] = v + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]; } } for (int k = 0; k < q; k++) { int r1, c1, r2, c2; scanf("%d %d %d %d", &r1, &c1, &r2, &c2); printf("%lld\n", P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]); } return 0;}첫줄 = コンソール.数読み();r = 첫줄[0];c = 첫줄[1];q = 첫줄[2]; // P[i][j] = 왼쪽 위 (1,1)부터 (i,j)까지 직사각형의 합. 0번째 줄·칸은 0으로 둔다P = [];繰り返す (i = 0; i <= r; i++){ P.追加(新リスト(c + 1, 0));}繰り返す (i = 1; i <= r; i++){ row = コンソール.数読み(); 繰り返す (j = 1; j <= c; j++) { P[i][j] = row[j - 1] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1]; }} 繰り返す (k = 0; k < q; k++){ qq = コンソール.数読み(); r1 = qq[0]; c1 = qq[1]; r2 = qq[2]; c2 = qq[3]; コンソール.書く(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]);}