ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1917. Titan Ruins: Deadly Accuracy

Test 22 Time limit exceeded! I need help
Posted by Egor14 24 Oct 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;
}