Submission #1005535

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
ll inf=1e18;
int N;
ll L[5000],R[5000];
ll dp[2][2501][2501];
int main(){
	cin>>N;
	rep(i,N) cin>>L[i]>>R[i];
	rep(i,N-1) rep(j,N-1) if(L[j]+R[j]<L[j+1]+R[j+1]) swap(L[j],L[j+1]),swap(R[j],R[j+1]);
	rep(i,2) rep(j,2501) rep(k,2501) dp[i][j][k]=inf;
	dp[0][0][0]=0;
	rep(n,N){
		rep(c,2) rep(l,n+1-c){
			int r=n-l-c;
			if(dp[c][l][r]==inf) continue;
			if(c==0) chmin(dp[1][l][r],dp[0][l][r]+N/2*(L[n]+R[n]));
			if(l<2500) chmin(dp[c][l+1][r],dp[c][l][r]+l*(L[n]+R[n])+R[n]);
			if(r<2500) chmin(dp[c][l][r+1],dp[c][l][r]+r*(L[n]+R[n])+L[n]);
		}
	}
	ll ans=inf;
	rep(c,2) rep(l,N+1-c){
		int r=N-l-c;
		if(l<=2500&&r<=2500) chmin(ans,dp[c][l][r]);
	}
	cout<<ans<<endl;
}

Submission Info

Judge Result