Submission #617180

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

int dp[2005][2005];
vector<int>x[2005];int cnt;
int s[2005], t[2005], N, L;
int X[2005][2005], c, minv, minid;

int main() {
	cnt = 0;
	cin >> N >> L;
	for (int i = 0; i < N; i++){
		cin >> t[i] >> s[i];
		if (i >= 1) {
			if (t[i] != t[i - 1]) {
				cnt++;
			}
		}
		x[cnt].push_back(s[i]);
	}
	cnt++;
	for (int i = 0; i < cnt; i++){
		c = 0;
		for (int j = 0; j <= L; j++) {
			for (int k = 0; k < x[i].size(); k++) {
				X[i][j] += abs(x[i][k] - j);
			}
		}
	}
	for (int i = 0; i < cnt; i++){
		minv = 1000000000; minid = 0;
		for (int j = 0; j <= L; j++) {
			if (minv > dp[i][j]) {
				minv = dp[i][j]; minid = j;
			}
		}
		for (int j = 0; j <= L; j++) {
			if (minid > j) {
				dp[i + 1][j] = dp[i][j] + X[i][j];
			}
			else {
				dp[i + 1][j] = minv + X[i][j];
			}
		}
	}
	minv = 1000000000;
	for (int i = 0; i <= L; i++) {
		minv = min(minv, dp[cnt][i]);
	}
	cout << minv << endl;
	return 0;
}

Submission Info

Judge Result