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

Обсуждение задачи 1917. Руины титанов: убийственная точность

Test 22 Time limit exceeded! I need help
Послано Egor14 24 окт 2014 00:23
Hi! I have time limit exceeded in test 22. What's wrong with my code? What is the best approach for this task? Maybe use stack? Thanks; My code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


//Get all possible spell power variants
vector<int> GetVariants(vector<int> vct)
{
    vector<int> answ;
    for(unsigned int i=0;i<vct.size();i++)
    {
        if(find(answ.begin(),answ.end(),vct[i])==answ.end())
            answ.push_back(vct[i]);
    }
    sort(answ.begin(), answ.begin()+answ.size());
    reverse(answ.begin(),answ.end());
    return answ;
}

//Get number or values, in vct which <= num (here it is destructable coins)
int GetNumberOfLowerOrEqual(vector<int> vct,int num)
{
    int number = 0;
    for(unsigned int i=0;i<vct.size();i++)
    {
        if(vct[i]<=num)number++;
    }
    return number;
}


int main()
{
    int n,p,curr;
    scanf("%d",&n);//initial size of coins vector
    scanf("%d",&p);// health
    vector<int> coins;
    vector<int> variants;

    int deleted = 0;
    int spells = 0;

    for(int i=0;i<n;i++)
    {
        scanf("%d",&curr);
        coins.push_back(curr);
    }

    variants = GetVariants(coins);
    bool dChanged = false;

    for(int times = 0; times<n && !coins.empty();times++)
    {
        for(int i=0;i<variants.size() && !coins.empty();i++)
        {
            if(GetNumberOfLowerOrEqual(coins,variants[i])*variants[i]<=p)//surrvived
            {
                dChanged = false;
                //here we remove all elements from coins, which <= variants[i]
                for(int t=0;t<coins.size();t++)
                {
                    if(coins[t] <= variants[i])
                    {
                        coins.erase(coins.begin()+t);
                        t--;
                        deleted++;
                        dChanged = true;
                    }
                }
                if(dChanged)
                {
                    spells++;//if anything changed, add spell
                    break;
                }

            }

        }
    }

    printf("%d ", deleted);
    printf("%d",spells);
    //system("pause");
    return 0;
}