Space Elevator

http://acm.pku.edu.cn/JudgeOnline/problem?id=2392

• 息抜きのつもりだったのに(´ω｀)

息抜きのつもりでやってみたものの、TLEに引っかかり悩む。高さ限度の値が小さい順にソートして、DPってかんじのコードを書いたら通らない。重複要素を入れないようにすれば速くなるしmemory limitにもかからんだろうってことで書き直したのに、通らない(;´д｀)うえーん。
で、しばらく大きなデータを食わせたりして調べてみて、あまりに遅すぎるわけではないことに気付いたので、乗算回数を減らしてギリギリAccept。しかし他の人たちはほとんどが200ms以内で通しているので、私のやり方がアホなのだろうか・・・。

以下、とりあえず通ったコード

typedef struct _T{
	int h,a,c;
}T;

T t[500];
int s[50000],v[50000],tb[40001];
int i,j,k,l,n,b,c,tmp;
q(T*a,T*b){return a->a-b->a;}
main(){
	scanf("%d",&n);
	for(i=0;i<n;++i)scanf("%d%d%d",&t[i].h,&t[i].a,&t[i].c);
	qsort(t,n,sizeof(T),q);

	l=1;
	for(i=0;i<n;++i){
		for(k=j=0;j<l;++j){
			for(b=0,c=t[i].c,tmp=s[j]-t[i].h;b<=c&&(tmp+=t[i].h)<=t[i].a;++b){
				if(tb[v[k] = tmp]!=i+1){
					tb[v[k]]=i+1;
					++k;
				}
			}
		}
		l=k;
		for(j=0;j<l;++j)s[j]=v[j];
	}
	for(i=j=0;i<l;++i)j=j>s[i]?j:s[i];
	printf("%d",j);
}