Задача
Задана матрица чисел $a_{ij}$ где $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$. Для всех $i, j$ найдите $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt}.$$
Входные данные
В первой строке записаны размеры матрицы — $n, m$ $(1 \leqslant n, m \leqslant 1000)$. В последующих $n$ строках записано по $m$ чисел $a_{ij}$ $(1 \leqslant a_{ij} \leqslant 1000)$.
Выходные данные
Выведите $n$ строк по $m$ чисел $S_{i,j}$.
Тесты
| Входные данные | Выходные данные |
| 3 5 1 2 3 4 5 5 4 3 2 1 2 3 1 5 4 |
1 3 6 10 15 6 12 18 24 30 8 17 24 35 45 |
| 4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
1 2 3 4 2 4 6 8 3 6 9 12 4 8 12 16 |
| 6 7 15 78 69 36 567 654 5 54 54 52 81 237 5 98 987 2 65 5 32 89 67 541 89 4 32 4 1 40 68 7 345 6 21 23 56 9 5 7 2 5 4 1000 |
15 93 162 198 765 1419 1424 69 201 322 439 1243 1902 2005 1056 1190 1376 1498 2334 3082 3252 1597 1820 2010 2164 3004 3753 3963 1665 1895 2430 2590 3451 4223 4489 1674 1909 2451 2613 3479 4255 5521 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> using namespace std; int x[1001][1001]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++) cin >> x[i][j]; } for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++) x[i][j] += x[i-1][j] + x[i][j-1] - x[i-1][j-1]; } for (int i = 1; i <= n; i++){ for (int j = 1; j <= m; j++){ cout << x[i][j]; if (j != m) cout << " "; } cout << endl; } return 0; } |
Решение
Создаем матрицу x[1001][1001] вне int main() . Сдвигаем индексацию массива на единицу и заполняем его. Таким образом первая строка и первый столбец у нас оказываются заполнены нулями. Чтобы не вычислять каждую новую $S_{i,j}$ от $(i+1)\cdot (j+1)$ предыдущих значений, воспользуемся основным свойством частичных сумм: если $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt},$$ то тогда $S_{i,j} — a_{ij}=S_{i-1,j}+S_{i,j-1}-S_{i-1,j}\cap S_{i,j-1}$, где $S_{i-1,j}\cap S_{i,j-1} = S_{i-1,j-1}$. Тогда при $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$ вычисляем частичные суммы по формуле: $$S_{i,j} = S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+a_{ij}.$$