Submission #1366778

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;

int n, l[401], r[401];
long long dp[401][401];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
	for(int i = 1; i <= n; i++) for(int j = 1; j <= 400; j++) dp[i][j] = INF;
	for(int j = 1; j <= 400; j++) dp[1][j] = abs(l[1] - j);
	for(int i = 2; i <= n; i++) for(int j = 1; j <= 400; j++) {
		for(int k = max(j-r[i-1]+1, 1); k <= min(j+r[i]-1, 400); k++) dp[i][j] = min(dp[i-1][k]+abs(j-l[i]), dp[i][j]);
	}
	long long ans = INF;
	for(int j = 1; j <= 400; j++) ans = min(dp[n][j], ans);
	cout << ans;
}

Submission Info

Judge Result