PKU 3042:Grazing on the Run

みなさんはくれぐれもこんなソースを書かないようにしましょう。
やってることは区間DP

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
pair<long long,long long> dp[1000][1000][2];
bool in[1000][1000][2];
int dat[1000];
struct wolf{
	int left;
	int right;
	int LR;
	wolf(int L,int R,int lr){
		left=L;
		right=R;
		LR=lr;
	}
};
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",dat+i);
	}
	std::sort(dat,dat+a);
	for(int i=0;i<1000;i++)
		for(int j=0;j<1000;j++)
			dp[i][j][0]=dp[i][j][1]=make_pair(1999999999LL,1999999999LL);
	int at=lower_bound(dat,dat+a,b)-dat;
	queue<wolf>Q;
	if(dat[at]==b){
		dp[at][at][0]=dp[at][at][1]=make_pair(0,0);
		Q.push(wolf(at,at,0));
		Q.push(wolf(at,at,1));
		in[at][at][0]=in[at][at][1]=true;
	}else{
		if(at<a)dp[at][at][0]=dp[at][at][1]=make_pair(dat[at]-b,dat[at]-b);
		if(at)dp[at-1][at-1][0]=dp[at-1][at-1][1]=make_pair(b-dat[at-1],b-dat[at-1]);
		if(at<a){
			Q.push(wolf(at,at,0));
			Q.push(wolf(at,at,1));
		}
		if(at){
			Q.push(wolf(at-1,at-1,0));
			Q.push(wolf(at-1,at-1,1));
		}
		if(at<a)in[at][at][0]=in[at][at][1]=true;
		if(at)in[at-1][at-1][0]=in[at-1][at-1][1]=true;
	}
	while(Q.size()){
		int left=Q.front().left;
		int right=Q.front().right;
		int LR=Q.front().LR;
		Q.pop();
		
		if(left&&!in[left-1][right][0]){
			in[left-1][right][0]=true;
			Q.push(wolf(left-1,right,0));
		}
		if(right<a-1&&!in[left][right+1][1]){
			in[left][right+1][1]=true;
			Q.push(wolf(left,right+1,1));
		}
		if(LR==0){
			if(left&&dp[left][right][LR].second+dp[left][right][LR].first+dat[left]-dat[left-1]+(dp[left][right][LR].first+dat[left]-dat[left-1])*(a-(right-left)-1)<dp[left-1][right][0].second+dp[left-1][right][0].first*(a-(right-left)-1)){
				dp[left-1][right][0]=make_pair(dp[left][right][LR].first+dat[left]-dat[left-1],dp[left][right][LR].second+dp[left][right][LR].first+dat[left]-dat[left-1]);
			}
			if(right<a-1&&dp[left][right][LR].second+dp[left][right][LR].first+dat[right+1]-dat[left]+(dp[left][right][LR].first+dat[right+1]-dat[left])*(a-(right-left)-1)<dp[left][right+1][1].second+dp[left][right+1][1].first*(a-(right-left)-1)){
				dp[left][right+1][1]=make_pair(dp[left][right][LR].first+dat[right+1]-dat[left],dp[left][right][LR].second+dp[left][right][LR].first+dat[right+1]-dat[left]);
			}
		}else{
			if(left&&dp[left][right][LR].second+dp[left][right][LR].first+dat[right]-dat[left-1]+(dp[left][right][LR].first+dat[right]-dat[left-1])*(a-(right-left)-1)<dp[left-1][right][0].second+dp[left-1][right][0].first*(a-(right-left)-1)){
				dp[left-1][right][0]=make_pair(dp[left][right][LR].first+dat[right]-dat[left-1],dp[left][right][LR].second+dp[left][right][LR].first+dat[right]-dat[left-1]);
			}
			if(right<a-1&&dp[left][right][LR].second+dp[left][right][LR].first+dat[right+1]-dat[right]+(dp[left][right][LR].first+dat[right+1]-dat[right])*(a-(right-left)-1)<dp[left][right+1][1].second+dp[left][right+1][1].first*(a-(right-left)-1)){
				dp[left][right+1][1]=make_pair(dp[left][right][LR].first+dat[right+1]-dat[right],dp[left][right][LR].second+dp[left][right][LR].first+dat[right+1]-dat[right]);
			}
		}
	}
	printf("%lld\n",min(dp[0][a-1][0].second,dp[0][a-1][1].second));
}

なにより驚いたことは1RE後に適当に直してすんなり通ってしまったことである。
実装時間は30分程度？