Submission #2074676

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define INF 1e+18
using namespace std;

signed main(){
	int n,l,t[2000],p[2000],dp[2010][2010];
	vector<int> ts,evt[2000];
	cin >> n >> l;
	if(n > 2000 || l > 2000) return 0;
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= l;j++) dp[i][j] = INF;
	}
	dp[0][0] = 0;
	for(int i = 0;i < n;i++){
		cin >> t[i] >> p[i];
		ts.push_back(t[i]);
	}
	ts.erase(unique(ts.begin(),ts.end()),ts.end());
	for(int i = 0;i < n;i++){
		int ind = lower_bound(ts.begin(),ts.end(),t[i]) - ts.begin();
		evt[ind].push_back(p[i]);
	}
	for(int i = 0;i < ts.size();i++){
		int tmp = INF;
		for(int j = 0;j <= l;j++){
			int sum = 0;
			tmp = min(tmp,dp[i][j]);
			for(int v : evt[i]) sum += abs(v - j);
			dp[i + 1][j] = tmp + sum;
			//cout << dp[i + 1][j] << " ";
		}
		//cout << endl;
	}
	int mi = INF;
	for(int i = 0;i <= l;i++) mi = min(mi,dp[ts.size()][i]);
	cout << mi << endl;
	return 0;
}

Submission Info

Judge Result