結果
問題 |
No.755 Zero-Sum Rectangle
|
ユーザー |
|
提出日時 | 2023-03-31 20:07:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 169 ms / 2,000 ms |
コード長 | 1,612 bytes |
コンパイル時間 | 1,772 ms |
コンパイル使用メモリ | 176,032 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-22 22:50:19 |
合計ジャッジ時間 | 2,983 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); array<array<int,130>,130> A{}; array<array<int,131>,131> B{}; int n, m; cin >> n >> m; for(int y = 0; y < m; y++){ for(int x = 0; x < m; x++){ cin >> A[y][x]; } } vector<pair<ll,int>> temp(m + 1); array<ll, 130> C{}; for(int ly = 0; ly < m; ly++){ C.fill(0); for(int ry = ly + 1; ry <= m; ry++){ temp[0] = make_pair(0, 0); for(int x = 0, y = ry - 1; x < m; x++){ C[x] += A[y][x]; temp[x + 1] = make_pair(temp[x].first + C[x], x + 1); } sort(temp.begin(), temp.end()); for(int i = 0; i < m; ){ int p = i++; while(i <= m && temp[i].first == temp[p].first) i++; for(int j = p; j + 1 < i; j++){ for(int k = j + 1; k < i; k++){ B[ry][temp[k].second]++; B[ly][temp[k].second]--; B[ry][temp[j].second]--; B[ly][temp[j].second]++; } } } } } for(int i = 0; i < 131; i++) { for(int j = 1; j < 131; j++) { B[i][j] += B[i][j - 1]; } } for(int i = 0; i < 131; i++) { for(int j = 1; j < 131; j++) { B[j][i] += B[j - 1][i]; } } while(n--){ int y, x; cin >> y >> x; cout << B[--y][--x] << '\n'; } }