skyaozoraの日記

AOJ2290 Attack the Moles

16:57

問題概要

問題文

日本語だし書くの面倒だから問題文を見て

解法

時刻t[i]に位置x[i]に現れるモグラを叩いた手で時刻t[j]に位置x[j]に現れるモグラを叩けるかどうかという条件は、

y[i]=t[i]*v-x[i]

z[i]=t[i]*v+x[i]

というy,zを利用するとy[i]<=y[j],z[i]<=z[j]と表すことができる(格子点に対して45度回転するやつの応用みたいな感じ)なので、モグラをy[i]の昇順でソートして、segtreeを使ってz[i]ある値以下の時の得点の最大値を求められるようにすれば、状態O(N^2),遷移O(logN)のDPができる。

ただし、両手で同じモグラを叩いて得点を2度カウントしてしまうということがないように遷移には注意が必要(自分はindexが小さいモグラを叩いた方の手から遷移する、ということにしたけど他にいい方法はあるのかな)

//JAG夏合宿11Day2F Attack the Moles(AOJ2290)
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<lint,lint> pint;
typedef pair<pint,int> tint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define N 4096
#define M 3010
int dat[M+10][N*2+10];
int dp[M+10][M+10];
int d2[M+10];
vector<lint> p0,p1,p2;
int inf=1001001001;
int query(int id,int a,int b,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return -inf;
	if(a<=l && r<=b) return dat[id][k];
	int vl=query(id,a,b,k*2+1,l,(l+r)/2);
	int vr=query(id,a,b,k*2+2,(l+r)/2,r);
	return max(vl,vr);
}
void update(int id,int k,int a){
	k+=N-1;
	dat[id][k]=a;
	while(k>0){
		k=(k-1)/2;
		dat[id][k]=max(dat[id][k*2+1],dat[id][k*2+2]);
	}
	return;
}
vector<tint> a;
lint x[M+10],t[M+10],t2[M+10];int p[M+10],po[M+10];
int main()
{
	int n,out=0;lint v;
	cin>>n>>v;cin>>x[n]>>x[n+1];
	p2.pb(x[n]);p2.pb(x[n+1]);
	p1.pb(-x[n]);p1.pb(-x[n+1]);
	a.pb(mp(mp(-x[n],x[n]),n));a.pb(mp(mp(-x[n+1],x[n+1]),n+1));
	rep(i,n){
		cin>>x[i]>>t[i]>>p[i];
		p1.pb(t[i]*v-x[i]);
		p2.pb(x[i]+t[i]*v);
		a.pb(mp(mp(t[i]*v-x[i],t[i]*v+x[i]),i));
	}
	sort(All(p1));p1.erase(unique(All(p1)),p1.end());
	sort(All(p2));p2.erase(unique(All(p2)),p2.end());
	
	rep(i,M+5) rep(j,N*2+5) dat[i][j]=-inf;
	rep(i,M) rep(j,M) dp[i][j]=-inf;rep(i,M) d2[i]=-inf;
	
	int x1,x2;
	sort(All(a));
	rep(i,a.size()){
		po[i]=p[a[i].se];
		t2[i]=lower_bound(All(p2),a[i].fi.se)-p2.begin();
		if(a[i].fi.fi==-x[n] && a[i].fi.se==x[n]) x1=i;
		if(a[i].fi.fi==-x[n+1] && a[i].fi.se==x[n+1]) x2=i;
	}
	dp[x1][x2]=dp[x2][x1]=0;
	rep(i,n+2){
		rep(j,i){
			dp[i][j]=max(dp[i][j],po[i]+query(j,0,t2[i]+1));
			dp[i][j]=max(dp[i][j],po[j]+query(i,0,t2[j]+1));
			update(i,t2[j],dp[i][j]);
			if(i==x1 || i==x2) update(j,t2[i],dp[i][j]);
			d2[i]=max(d2[i],dp[i][j]);
			out=max(out,dp[i][j]);
		}
	}
	rep(i,n+2) rep(j,i){
		if(t2[j]<=t2[i]) d2[i]=max(d2[i],d2[j]+po[i]);
		out=max(out,d2[i]);
	}
	cout<<out<<endl;
}