Ускорить программу

[nikitosoleil]

Не проходит половину тестов из-за превышения по времени. Как оптимизировать работу в такой элементарной программе?
Условие задачи:
Для проведения чемпионата Европы по футболу в Португалии было принято
решение построить К-цветной цифровой экран NxM (N по вертикали, M по
горизонтали) пикселей. Но в связи с тем, что экран очень большой, работать
можно только с прямоугольной областью экрана N1xM1 (N1 по вертикали, M1 по
горизонтали) пикселей. Экран был сконструирован так, что при его включении
цвета пикселям предоставляются случайным образом, а нужно, чтобы все пиксели были
черного (0-го) цвета. Вам необходимо определить минимальное количество операций,
необходимую для того, чтобы сделать из исходного экрана экран черного (0-го) цвета,
или указать, что решения не существует. За одну операцию считается: взять
прямоугольную область экрана N1xM1 (N1 по вертикали, M1 по горизонтали) пикселей,
полностью принадлежит экрана, и все номера цветов этой области увеличить на
единицу по модулю K (т.е. если номер цвета равна K-1, то после увеличение станет 0).
С консоли вводятся: в первой строке два числа через пробел N и M -
размеры экрана; во второй строке - два числа N1 и M1 - размеры прямоугольной
области, в третьей строке - одно число K- количество цветов на экране. Далее следуют
строк N по M чисел, разделенные пробелами, - номере цветов в палитре (все числа
от 1 до K).
Ограничения 1≤N1≤N≤1000, 1≤M1≤M≤1000, 2≤K≤1000.
В консоль вывести минимальное количество операций.
Мое решение:

#include <iostream>
 
using namespace std;
 
const int MAX=1000;
 
void upgrade(int arr[MAX][MAX], int i, int j, int n, int m, int n1, int m1, int k);
 
int main()
{
    int N, M, N1, M1, K, counter=0;
    cin >> N;
    cin >> M;
    cin >> N1;
    cin >> M1;
    cin >> K;
    int arr[MAX][MAX];
    for (int i=0; i<N; i++)
        for (int j=0; j<M; j++)
            cin >> arr[j][i]; ///Ввод
    for (int i=0; i<N-N1+1; i++)
        for (int j=0; j<M-M1+1; j++)
            while(arr[j][i]!=0)
            {
                upgrade(arr, j, i, N, M, M1, N1, K);
                counter++;
            }
    for (int i=0; i<N; i++)
        if (arr[i][M-1]!=0) { cout << "impossible"; return 0; }
    for (int i=0; i<M; i++)
        if (arr[N-1][i]!=0) { cout << "impossible"; return 0; }
    cout << counter;
    return 0;
}
 
void upgrade(int arr[MAX][MAX], int x, int y, int n, int m, int n1, int m1, int k)
{
    for (int i=0; i<n1; i++) ///Увеличиваем все значения в выбранном прямоугольнике на 1
        for(int j=0; j<m1; j++)
            arr[i+x][j+y]=(arr[i+x][j+y]+1)%k; ///Если переполнение - остаток от деления на кол-во цветов
}

[f.hump]

ну, например

arr[i+x][j+y]=(arr[i+x][j+y]+1)%k;

заменить на

for (++arr[i+x][j+y];arr[i+x][j+y]>=k;arr[i+x][j+y]-=k);

и если заполнение массива происходит по колонкам, то и хранить его имеет смысл не построчно, а поколоночно.


прочитал условие задачи. что-то подсказывает, что предложенное решение - решение влоб, и быстрым никогда не будет. принимая во внимание, что состояние пикселей можно прочитать, возможно имеет смыл перед началом операций провести анализ экрана на наличие областей однго цвета. также подумалось, что для ответа на вопрос о существовании решения проводить перестройку экрана не нужно.

[BDA]

Согласен с f.hump, что это решение в лоб.
Если ускорять именно это решение, то заменил бы while(arr[j][i]!=0) на расчет сразу необходимого числа шагов для пикселя arr[j][i] и потом уже делал upgrade и увеличивал counter на это число шагов. Насчет текущей проверки impossible не согласен - по-моему, может быть ситуация, что крайние строка и столбец нулевые, а "кое-какие" элементы все же нет. После "полного" апгрейда (зануление левого верхнего угла экрана) ненулевые пиксели могут остаться в M1-1 крайних столбцах и N1-1 крайних строках.