Submission #2074510

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int N,L,t[2009],p[2009],dp[2009][2009];

int main(){
	cin>>N>>L;
	for(int i=1;i<=N;i++) cin>>t[i]>>p[i];
	t[N+1]=1000000007;p[N+1]=L;
	for(int i=0;i<2009;i++){for(int j=0;j<2009;j++) dp[i][j]=(1<<30);}
	dp[0][0]=0;
	for(int i=1;i<=N+1;i++){
		for(int j=0;j<=L;j++) dp[i][j]=dp[i-1][j];
		if(t[i-1]<t[i]){
			for(int j=1;j<=L;j++) dp[i][j]=min(dp[i][j], dp[i][j-1]);
		}
		for(int j=0;j<=L;j++) dp[i][j]+=abs(p[i]-j);
	}
	cout<<dp[N + 1][L]<<endl;
	return 0;
}

Submission Info

Judge Result