ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1097. Квадратная страна 2

Help!!! TLE!!!!, Any good idea to speed up???
Послано MultiThread 8 окт 2006 14:24
#include <stdio.h>
#include <string.h>

const int MAXM = 100;


struct Occupied
{
    int x;
    int y;
    int size;
    int im;
};

Occupied occupied[MAXM]= {0};

void main ()
{
    int L = 0;
    int A = 0;
    int M = 0;

    //FILE * fin = fopen ("E:/Algorithm/Timus/data.txt", "r");
    FILE * fin = stdin;

    fscanf (fin, "%d%d%d", &L, &A, &M);

    int i = 0;
    int j = 0;
    int k = 0;

    for (i = 0; i < M; i++)
    {
        fscanf (fin, "%d%d%d%d", &occupied[i].im, &occupied[i].size, &occupied[i].x, &occupied[i].y);
    }

    int max = 0;
    int min = 0;

    for (i = 1; i <= L - A + 1; i++)
    {
        for (j = 1; j <= L - A + 1; j++)
        {
            int max = 0;
            bool contain255 = false;
            bool intersected = false;
            for (k = 0; k < M; k++)
            {
                if (occupied[k].x + occupied[k].size -1 < i || occupied[k].y + occupied[k].size - 1 < j ||
                    occupied[k].x > i + A - 1 || occupied[k].y > j + A -1)
                {
                    continue;
                }
                intersected = true;

                if (occupied[k].im == 255)
                {
                    contain255 = true;
                    break;
                }

                if (max == 0 || occupied[k].im > max)
                {
                    max = occupied[k].im;
                }
            }

            if (!contain255 && !intersected)
            {
                max = 1;
            }

            if (!contain255)    1
            {
                if (max != 0 && (max < min || min == 0))
                {
                    min = max;
                }
            }

        }
    }

    if (min > 100 || min == 0)
    {
        printf ("IMPOSSIBLE");
    }
    else
    {
        printf ("%d\n", min);
    }
}
Re: Help!!! TLE!!!!, Any good idea to speed up???
Послано shrek 19 окт 2006 23:59
think about the property which the desired square should have and it's relation with the m squares. It should be bounded in some ways.