Как уменьшить время выполнения с 1 секунды хотябы до 100 мс в легчайшем алгоритме?

Question

Решил написать простую программу в целях обучения и практики. Решение правильное, но очень медленное. Сдаю задачку на сайте, 13 из 27 тестов выдаёт около 2 секунд, а нужно меньше 1 секунды. Постарался максимально сократить все if-ы, которые только возможно было, но и это не помогает. Думаю, что основное время затрачивается на прокрутку цикла, но иначе задачу не решить же. У других пользователей среднее время в этой задачке от 14 до 100 мс. Я просто недавно начал, и может этот алгоритм который я написал совсем никак не ускорить, но по другому я просто не представляю как можно это решить.

условие задачи

Новый русский Витек приватизировал участок в Междолине размером m квадратов с севера на юг и n квадратов с запада на восток. Он решил построить в пределах этого участка дом размером a квадратов с севера на юг и b – с запада на восток. Некоторые квадраты радиоактивны, и Витек не хочет на них строить дом. Кроме того, Витек хочет, чтобы расстояния от стен до границ участка выражалась целым числом квадратов. Долго выбирал он место для дома, но так и не выбрал – слишком много вариантов. А сколько? Начал наш герой считать, но не сумел – плохо математику учил. Помогите ему.

Входные данные Напишите программу, которая считывает числа m, n, a, b, k (1 ≤ a ≤ m ≤ 5000, 1 ≤ b ≤ n ≤ 5000, 0 ≤ k ≤ m * n), где m, n – размеры участка, a и b – размеры дома, k – количество радиоактивных квадратов, а затем k неповторяющихся пар чисел i и j (1 ≤ i ≤ m, 1 ≤ j ≤ n), которые определяют координаты радиоактивных квадратов.

Выходные данные Вывести искомое количество способов расположения дома.

На С++

#include <iostream>


using namespace std;

int main()
{

    int m, n, a, b, k, S, Ox, Oy, Oxmain = 1, Oymain = 1, l, t;  // m висота n ширина; a висота b ширина
    bool y = false;
    cin >> m >> n >> a >> b >> k;
    int i[100000];
    for (l = 1; l <= k * 2; l += 2)  
    {
        cin >> i[l] >> i[l + 1];
    }


    S = a * b;
    l = 0;

        while (Oymain <= ((m - a) + 1))
        {
            Oy = Oymain;
            while (Oxmain <= ((n - b) + 1))
            {
                Ox = Oxmain;
                for (Ox; Ox <= b + Oxmain - 1; Ox++)
                {
                    for (Oy; Oy <= a + Oymain - 1; Oy++)
                    {
                        for (t = 1; t <= k * 2; t += 2)
                        {
                            if ((Oy == i[t]) and (Ox == i[t + 1]))
                            {
                                y = true;
                                Ox = n;
                                continue;
                            }
                        }


                    }
                
                    Oy = Oymain;
                }
                if (y);
                else l++;
                y = false;
            
                Oxmain++;
            }
            Oxmain = 1;
            Oymain++;
        }


    cout << l << endl;

}

Answer 1

Создадим матрицу размером m x n, заполним её нулями и единицами (где радиоактивность).

Теперь посчитаем в ней же кумулятивные суммы - A[r][c] содержит количество единиц в прямоугольника 0,0-r,c (пример на Python, как это сделать за n*m).

Теперь пройдём по ячейкам матрицы, определяя, сколько единиц находится в прямоугольнике размером a x b с правым нижним углом в r,c, используя формулу

Cnt = A[r][c] + A[r-a][c-b] - A[r-a][c] - A[r][c-b]

(как это работает или здесь)

Количество прямоугольников с нулевой суммой - нужный результат

Answer 2

Можно решить от обратного: посчитать число клеток рядом с границами участка, куда дом точно не поместится и отметить клетки вокруг радиоактивных, на расстоянии размеров дома, где тоже нельзя строить. Оставшиеся клетки и будут результатом. Есть идеи как ещё оптимизировать. Можно ссылку на сайт где код запустить?

#include <iostream>
#include <vector>
#include <utility>


int main()
{
  int m, n; // размеры участка
  int a, b; // размеры дома
  int k;    // количество рад. квадратов

  std::cin >> m >> n >> a >> b >> k;

  std::vector<std::pair<int, int>> rad_cells(k);
  for (int i = 0; i < k; i++) {
    std::cin >> rad_cells[i].first >> rad_cells[i].second;
  }

  std::vector<char> world(m * n);

  int result = m * n; // общее число клеток
  result -= m*(b-1) + (n-b+1)*(a-1); // вычитаем клетки у правой и нижней
                                     // границы, где дом не поместится

  for (auto& cell: rad_cells) {
    int rad_x = cell.first - 1,  // координата радиоактивной клеки
        rad_y = cell.second - 1;

    // обходим радиоактивную клетку слева и свеху
    for (int dx = 0; dx < a; dx++) {
      int x  = rad_x - dx;
      if (x < 0) break;
      if (x > m - a) continue; // правая граница

      for (int dy = 0; dy < b; dy++) {
        int y  = rad_y - dy;
        if (y < 0) break;
        if (y > n - b) continue; // нижняя граница

        auto& point = world[x + y*m];

        if (point == 0) {
          // эту клетку ещё не считали
          point = 1;
          result--;
        }
      }
    }
  }

  std::cout << result << std::endl;
  
  return 0;
}

БЛОГ НА HUSL

Как уменьшить время выполнения с 1 секунды хотябы до 100 мс в легчайшем алгоритме?

Ответы (2 шт):