Submission #4272262

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

bool cmp(const ii &a, const ii &b)
{
	ll lena = a.se-a.fi; ll lenb = b.se-b.fi;
	if(lena!=lenb) return lena>lenb;
	else return a.fi<b.fi;
}

ll pref[5011][5111];
ll suf[2][5111];

void amin(ll &a, ll b)
{
	a=min(a,b);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	if(n==1){cout<<0<<'\n'; return 0;}
	vector<ii> vec;
	for(int i=0;i<n;i++)
	{
		ll l,r; cin>>l>>r;
		vec.pb({-l,r});
	}
	sort(vec.begin(),vec.end(),cmp);
	/*
	for(int i=0;i<n;i++)
	{
		cerr<<vec[i].fi<<' '<<vec[i].se<<'\n';
	}
	*/
	ll ans = ll(2e18);
	for(int l=(n-1)/2;l<=n/2;l++)
	{
		int r=n-1-l;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<=n;j++)
			{
				pref[i][j]=ll(1e18);
			}
		}
		for(int i=0;i<2;i++)
		{
			for(int j=0;j<=n;j++)
			{
				suf[i][j]=ll(1e18);
			}
		}
		pref[0][0]=vec[0].se;
		pref[0][1]=-vec[0].fi;
		for(int i=0;i+1<n;i++)
		{
			for(int j=0;j<=n;j++)
			{
				if(pref[i][j]<ll(1e18))
				{
					ll v=pref[i][j];
					ll L=vec[i+1].fi; ll R=vec[i+1].se;
					//go left
					amin(pref[i+1][j], v+R+ll(i+1-j)*(R-L));
					//go right
					amin(pref[i+1][j+1], v-L+ll(j)*(R-L));
				}
			}
		}
		suf[(n-1)&1][0]=vec[n-1].se+ll(l-1)*(vec[n-1].se-vec[n-1].fi);
		suf[(n-1)&1][1]=-vec[n-1].fi+ll(r-1)*(vec[n-1].se-vec[n-1].fi);
		for(int i=max(n-2,0);i<n;i++)
		{
			//segment i is fixed
			ll constant = vec[i].se*r-vec[i].fi*l;
			for(int j=0;j<=r;j++)
			{
				ll lef = 0; 
				ll ri = 0;
				if(i==0)
				{
					if(j!=0) lef=ll(1e18);
				}
				else lef=pref[i-1][j];
				if(i==n-1)
				{
					if(r-j!=0) ri=ll(1e18);
				}
				else ri=suf[(i+1)&1][r-j];
				//cerr<<i<<' '<<j<<' '<<constant<<' '<<lef<<' '<<ri<<'\n';
				ans = min(ans, constant+lef+ri);
			}
		}
		for(int i=n-1;i>0;i--)
		{
			int cur=(i+1)&1; int pre=cur^1;
			for(int j=0;j<=n;j++) suf[cur][j]=ll(1e18);
			for(int j=0;j<=n;j++)
			{
				if(suf[pre][j]<ll(1e18))
				{
					ll v=suf[pre][j];
					ll L=vec[i-1].fi; ll R=vec[i-1].se;
					//go left
					amin(suf[cur][j], v+R+ll(l-1-((n-1-i)+1-j))*(R-L));
					//go right
					amin(suf[cur][j+1], v-L+ll(r-1-j)*(R-L));
				}
			}
			{
				int i2=i-2;
				if(i2<0) continue;
				ll constant = vec[i2].se*r-vec[i2].fi*l;
				for(int j=0;j<=r;j++)
				{
					ll lef = 0; 
					ll ri = 0;
					if(i2==0)
					{
						if(j!=0) lef=ll(1e18);
					}
					else lef=pref[i2-1][j];
					if(i2==n-1)
					{
						if(r-j!=0) ri=ll(1e18);
					}
					else ri=suf[cur][r-j];
					//cerr<<i<<' '<<j<<' '<<constant<<' '<<lef<<' '<<ri<<'\n';
					ans = min(ans, constant+lef+ri);
				}
			}
		}
	}
	
	cout<<ans<<'\n';
}

Submission Info

Judge Result