e-olymp 683. Частичная сумма матрицы

Задача

Задана матрица чисел $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

Код программы

 

Решение

Создаем  матрицу 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}.$$

Ссылки

Условие задачи на E-olymp

Код программы на IdeOne

2 thoughts on “e-olymp 683. Частичная сумма матрицы

  1. Если сдвинуть индексацию массивов на 1 (начинать не с нуля а с единицы) и создать массив над мейном, тоесть выделять память не из кучи, а из стейка, то получится что x[I][j] = x[i-1][j] + x[I][j-1] -x[i-1][j-1] +a[I][j] верно для всех [I][j] и не нужно заполнять отдельно первый ряд и первый столбец, тоесть на самом деле задача решается в один цикл, содержащий в себе сразу ввод подсчет на прямоугольнике и вывод

Добавить комментарий