ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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)
{