4568195_ac_47ms_264k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 42 行

////////////////////////////////////
// Problem ID:1036 User Id:Epic
// Memory 32K Time:200MS
////////////////////////////////////
#include <iostream>
#include <stdlib.h>
//#include <search.h>
using namespace std;
int N,K,T;
int max_m;
struct Gangster{
	int s,p,t;
};
Gangster g[100];
int best[100];
int compare(const void* a, const void* b) {
	if ( ((Gangster*)a)->t<((Gangster*)b)->t ) return -1;
	if ( ((Gangster*)a)->t>((Gangster*)b)->t ) return 1;
	return 0;
}
int main()
{
	cin>>N>>K>>T;
	int i;
	for ( i=0; i<N; i++) cin>>g[i].t;
	for ( i=0; i<N; i++) cin>>g[i].p;
	for ( i=0; i<N; i++) cin>>g[i].s;
	qsort(g, N, sizeof(Gangster), compare);
	max_m = 0;
	for ( i=0; i<N; i++) {
		best[i] = -1;
		if ( g[i].t>=g[i].s ) best[i] = 0;
		int j,dt,ds;
		for ( j=0; j<i; j++)
			if ( ( best[j]>best[i] ) && (dt = g[i].t-g[j].t)>=(ds=g[i].s-g[j].s) && dt>=-ds )
				best[i] = best[j];
		if ( best[i]>=0 ) best[j] += g[i].p;
		if ( best[i]>max_m ) max_m = best[i];
	}
	cout<<max_m;
	return 0;
}