Submission #1005529


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][5001][5001];
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,N+1) rep(k,N+1) 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]));
			chmin(dp[c][l+1][r],dp[c][l][r]+l*(L[n]+R[n])+R[n]);
			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;
		chmin(ans,dp[c][l][r]);
	}
	cout<<ans<<endl;
}

Submission Info

Submission Time
Task F - Intervals
User sigma425
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1292 Byte
Status MLE
Exec Time 959 ms
Memory 391168 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 2
AC × 12
MLE × 33
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt MLE 945 ms 391040 KB
001.txt AC 178 ms 86272 KB
002.txt MLE 959 ms 391040 KB
003.txt MLE 738 ms 328448 KB
004.txt MLE 947 ms 391040 KB
005.txt AC 365 ms 168320 KB
006.txt MLE 948 ms 391040 KB
007.txt AC 474 ms 215552 KB
008.txt MLE 945 ms 391040 KB
009.txt AC 89 ms 46208 KB
010.txt MLE 946 ms 391040 KB
011.txt AC 407 ms 186624 KB
012.txt MLE 948 ms 391040 KB
013.txt AC 72 ms 38784 KB
014.txt MLE 949 ms 391040 KB
015.txt AC 179 ms 87168 KB
016.txt MLE 947 ms 391040 KB
017.txt MLE 717 ms 322304 KB
018.txt MLE 946 ms 391040 KB
019.txt AC 451 ms 205056 KB
020.txt AC 2 ms 256 KB
021.txt AC 2 ms 256 KB
022.txt MLE 928 ms 391040 KB
023.txt MLE 938 ms 391040 KB
024.txt MLE 932 ms 391040 KB
025.txt MLE 936 ms 391040 KB
026.txt MLE 935 ms 391040 KB
027.txt MLE 938 ms 391040 KB
028.txt MLE 931 ms 391040 KB
029.txt MLE 939 ms 391040 KB
030.txt MLE 933 ms 391040 KB
031.txt MLE 938 ms 391040 KB
032.txt MLE 932 ms 391040 KB
033.txt MLE 938 ms 391040 KB
034.txt MLE 937 ms 391040 KB
035.txt MLE 938 ms 391040 KB
036.txt MLE 931 ms 391168 KB
037.txt MLE 938 ms 391040 KB
038.txt MLE 936 ms 391040 KB
039.txt MLE 936 ms 391040 KB
040.txt MLE 940 ms 391040 KB
041.txt MLE 945 ms 391040 KB
042.txt MLE 936 ms 391168 KB
example0.txt AC 2 ms 256 KB
example1.txt AC 3 ms 384 KB