Submission #1748672

---

Source Code Expand

#include <bits/stdc++.h>
#define N 200010
#define BD 410
using namespace std;

inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
int n,L[N],R[N],F[N],G[N],len[N];
int main()
{
	n=read(); if(n>500) assert(0);
	for(int i=1;i<=n;i++)
		L[i]=read(), R[i]=read();
	for(int i=1;i<=n;i++) if(L[i]>R[i]) swap(L[i],R[i]);
	for(int i=1;i<=n;i++) len[i]=R[i]-L[i];
	for(int i=1;i<=BD;i++) G[i]=fabs(L[1]-i);
	for(int i=2;i<=n;i++)
	{
		memset(F,0x3f,sizeof F);
		for(int j=1;j<=BD;j++)
		{
			for(int k=1;k<=BD;k++)
			{
				if(k>j+len[i-1]||k+len[i]<j) continue;
				else F[k]=min(F[k],G[j]+abs(L[i]-k));
			}
		}
		for(int i=1;i<=BD;i++) G[i]=F[i];
		//for(int i=1;i<=BD;i++) printf("%d ",F[i]); printf("\n");
	}
	int Ans=0x3fffffff; for(int i=1;i<=BD;i++) Ans=min(Ans,G[i]);
	cout << Ans << endl;
	return 0;
}

Submission Info

Judge Result