задачка с acm.uva.es :)

From

Alexey Burdin (2:5012/2.89)

To

Oleg I. Khovayko

Date

2002-12-13T22:51:26Z

Area

RU.ALGORITHMS

> from: /Unknown/
Как после вчерашнего, Oleg ?

 19:05 Понедельник Декабрь 09 2002, Oleg I. Khovayko --> Anthony Volkov:

 OK> А быстро сумму прямоугольника считать можно вот как:

 OK> 1. Заводим дополнительную таблицу "с рамочкой" размером 102x102 из
 OK> int-ов, где каждая клетка x[i+1,j+1] содержит сумму чисел в
 OK> прямоугольнике (0,0,i,j).
 OK> 2. Легко видеть, что сумма любого прямоугольника (I,J,i,j) есть:
 OK> S = x[i+1,j+1] + x[I,J] - x[I,j+1] - x[i+1,J]
 OK> (I,J) - левый верхний угол, (i,j) - правый нижний.
    У меня точно такой же метод :)
    Может есть и тут чего соптимизировать? Пока не видно.

    2All: Сорри, я его уже знал :) Я думал что получше можно придумать.
          Хотя задачка предназначалась всем. По-моему, интересная :)
          Тут почты не было дня 3, сорри, что не отвечал

                Всего хорошего. Alexey.
... А что подyмал кpолик, никто не yзнал,
--- потомy что кpолик был очень воспитанный.
 * Origin: I want some help (2:5012/2.89)