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

@nikitosoleil · Регистрация: 24.07.2015

Author24 — интернет-сервис помощи студентам

Не проходит половину тестов из-за превышения по времени. Как оптимизировать работу в такой элементарной программе?
Условие задачи:

Кликните здесь для просмотра всего текста

Для проведения чемпионата Европы по футболу в Португалии было принято
решение построить К-цветной цифровой экран 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.
В консоль вывести минимальное количество операций.

Мое решение:

Кликните здесь для просмотра всего текста

C++

#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; ///Если переполнение - остаток от деления на кол-во цветов
}

	04.10.2015, 13:44