# SPOJ problem, DOTAA

I’ve solved DOTAA with time complexity of O(n*m)

Is there a better method?
Comment says, we can solve using some STL container, which one is it?

O(n *m)?

pre<
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
int t;
cin>>t;
while(t--)
{
int nh, twr,dmg;
cin>>nh>>twr>>dmg;
int i,arr[nh],ans=0;
for(i=0;i<nh;i++)
{
cin>>arr[i];

ans+= (arr[i]/dmg );
if(arr[i]%dmg==0)
ans-=1;

}
if (ans>=twr)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}

return 0;
}>

I don’t know the complexity of my code (lolmenub XD). I think O(T*n)? It ran in 0.04 sec.

What did you do? Did you also do something similar? Or something else?

(BTW : Dota is lyfff. Dotaa is louvvvvv <3333333 )

2 Likes

@vijju123’s approach is correct in \mathcal{O}(n) and there cannot be any better/faster way. If I had to guess, I would say the comment on the SPOJ problem page refers to using a priority queue to always bring forward the hero with the highest health to tank the tower damage for each tower, but that would be \mathcal{O}(n+m\;log\;n). Anyway, always good to see another DOTA player

2 Likes

You play dota too???!!! Niceeeee!!! XD

http://ideone.com/LyzzJk link to my very naive solution, you’re approach is good, didn’t thnk it that way!

Thank you, I’m implement this!

I see, so you ran a full check. That’s nice, had the Q asked something else which needed the current health of heroes after every step, your approach would score way higher than mine

1 Like
//