Tổng Hình Chữ Nhật - LCOJ: Luyện Code Online Judge

SUMHCN - Tổng Hình Chữ Nhật

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

aprocoder

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho một bảng gồm m hàng và n cột.

Cho t yêu cầu có dạng a b c d, với mỗi yêu cầu, in ra tổng các số trong bảng chữ nhật con có hai góc đối diện là ô (a,b) và ô (c,d).

Input

Dòng đầu tiên chứa ba số nguyên dương m, n và t (1 ≤ m, n ≤ 200,1 ≤ t ≤ 40000).

Tiếp theo, mỗi dòng chứa n số nguyên là các phần tử của bảng.Các số này có trị tuyệt đối không quá ~ 10^9 ~.

Tiếp theo, mỗi dòng chứa bốn số nguyên a, b, c, d mô tả một yêu cầu (1 ≤ a ≤ c ≤ m, 1 ≤ b ≤ d ≤ n).

Output

Với mỗi yêu cầu, in ra tổng các số trong bảng chữ nhật con.

Sample

Input #1

Output #1

1
-1
0
-2
-7
-2
-23

Problem source: apok

Bình luận

Please read the guidelines before commenting.

full ac

include <bits/stdc++.h>

using namespace std;

int main() { iosbase::syncwith_stdio(0); cin.tie(0); int m, n, t; while (cin >> m >> n >> t) { vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            long long val;
            cin >> val;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + val;
        }
    }

    while (t--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        long long ans = dp[c][d] - dp[a - 1][d] - dp[c][b - 1] + dp[a - 1][b - 1];
        cout << ans << '\n';
    }
}
return 0;

}

0

dinhvantung0611 đã bình luận lúc 15, Tháng 3, 2024, 18:39

Sao bài này lại được xếp vào dạng bài 3 điểm vậy. Code trâu cũng đã AC rồi, chưa cần miếng tư duy nào luôn