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

Обсуждение задачи 1167. Bicolored Horses

my algo with O(N) get WA#1!!
Послано Bobur 24 ноя 2008 01:55
  please help, i can't find my mistake!!!
Re: my algo with O(N) get WA#1!!
Послано Mihran Hovsepyan {2 kurs of <RAU>} 30 янв 2009 02:58
My algorithm is O(n*(n-k)) but I can't pass test 1 too, Help me, if you can.

this is my code.

# include <iostream>
using namespace std;

int main ()
{
    char a;
    int min,num,n,k,i,ans=0;
    int w[510]={0};
    int b[510]={0};
    cin>>n>>k;
    for(i=0;i<n;i++)
    {
        cin>>a;
        if(a=='0')
            b[i]=1;
        else
            w[i]=1;
    }
    while(n>k)
    {
        min=2147483647;
        for(i=0;i<n-1;i++)
            if(min>w[i]*b[i+1]+w[i+1]*b[i])
            {
                min=w[i]*b[i+1]+w[i+1]*b[i];
                num=i;
            }
        w[num]+=w[num+1];
        b[num]+=b[num+1];
        for(i=num+1;i<n;i++)
        {
            w[i]=w[i+1];
            b[i]=b[i+1];
        }
        n--;
        ans+=min;
    }
    cout<<ans<<endl;
    return 0;
}