比赛 20120615 评测结果 WAAAWWWWWT
题目名称 新打鼹鼠 最终得分 30
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-06-15 16:50:57
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <set>

#define I_F "strike.in"
#define O_F "strike.out"

const long Maxm=100000;
const short P=20;

struct strike
{
	long t,w,x;
};
struct dyna
{
	long l;
	long long w;
};

long n,m;
short p;
strike s[Maxm];
long long ans;

void Input();
template<typename Any>
inline void Swap(Any&, Any&);
void Sort(const long&, const long&);
inline bool operator<(const dyna&, const dyna&);
template<typename Any>
inline Any Max(const Any&, const Any&);
inline long Abs(const long&);
void Dynap();
void Output();

int main()
{
	Input();
	Sort(0,m-1);
	Dynap();
	Output();
	return 0;
}

void Input()
{
	freopen(I_F,"r",stdin);
	scanf("%ld%ld%hd",&n,&m,&p);
	for (long i=0; i<m; ++i)
		scanf("%ld%ld%ld",&s[i].t,&s[i].w,&s[i].x);
}

template<typename Any>
inline void Swap(Any &a, Any &b)
{
	Any t=a;
	a=b;
	b=t;
}

inline long Abs(const long &x)
{
	return (x<0)?-x:x;
}

void Sort(const long &l, const long &r)
{
	if (r-l>P)
	{
		long x=s[l+rand()%(r-l+1)].t;
		long i=l, j=r;
		do
		{
			while (s[i].t<x) ++i;
			while (s[j].t>x) --j;
			if (i<=j)
				Swap(s[i++],s[j--]);
		} while (i<j);
		if (i<r) Sort(i,r);
		if (l<j) Sort(l,j);
	}
	else
	{
		bool flag=true;
		for (long i=l; i<r && flag; ++i)
		{
			flag=false;
			for (long j=r; j>i; --j)
				if (s[j].t<s[j-1].t)
					Swap(s[j],s[j-1]),
					flag=true;
		}
	}
}

inline bool operator<(const dyna &a, const dyna &b)
{
	return a.w>b.w;
}

template<typename Any>
inline Any Max(const Any &a, const Any &b)
{
	return (a>b)?a:b;
}

void Dynap()
{
	std::set<dyna> f;
	f.clear();
	dyna t1, t2;
	t1.l=0;
	t1.w=s[0].w;
	f.insert(t1);
	ans=t1.w;
	for (long i=1; i<m; ++i)
	{
		t2.w=0;
		for (std::set<dyna>::iterator j=f.begin(); j!=f.end() && t2.w==0; ++j)
			if (Abs(s[j->l].x-s[i].x)<=p*(s[i].t-s[j->l].t))
				t2=*j;
		t1.w=s[i].w+t2.w;
		t1.l=i;
		f.insert(t1);
		ans=Max(ans,t1.w);
	}
}

void Output()
{
	freopen(O_F,"w",stdout);
	printf("%lld\n",ans);
}