Submission #2169503


Source Code Expand

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=(int)1000000007;
const llint big=(llint)(2.19e15)+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
using pli=pair<llint,int>;
using daic=priority_queue<pli,vector<pli>,greater<pli>>;
int main(void){
	//ダイナミックプログラミンッ!!!
	int i,j,n;cin>>n;
	static llint dp[2505][2505]={0};
	vector<tuple<llint,llint,llint>> kuka(n);
	for(i=0;i<n;i++){
		llint L,R;cin>>L>>R;
		kuka[i]=mt(L+R,L,R);
	}
	SO(kuka);REV(kuka);
	//でかい奴から両端に埋めていく
	//(n/2個) ((n+1)/2個) になる
	dp[0][0]=-big;
	for(i=0;i<n-n%2;i++){
		for(j=0;j<=i;j++){
			int hi=j;
			int mg=i-j;
			if(n/2<hi){continue;}
			if((n+1)/2<mg){continue;}
			llint wa,L,R;
			tie(wa,L,R)=kuka[i];
			mineq(dp[hi+1][mg],dp[hi][mg]+hi*wa+L);
			mineq(dp[hi][mg+1],dp[hi][mg]+mg*wa+R);
		}
	}
	if(n%2==1){
		dp[n/2][n/2]+=get<0>(kuka[n-1])*(n/2);
	}
	cout<<dp[n/2][n/2]+big<<endl;
	RE;
}

Submission Info

Submission Time
Task F - Intervals
User WA_TLE
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2751 Byte
Status WA
Exec Time 51 ms
Memory 49280 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 2
AC × 16
WA × 29
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 WA 47 ms 37120 KB
001.txt AC 13 ms 22016 KB
002.txt WA 49 ms 47488 KB
003.txt WA 39 ms 43392 KB
004.txt WA 47 ms 37120 KB
005.txt AC 22 ms 30592 KB
006.txt AC 51 ms 49280 KB
007.txt AC 27 ms 34944 KB
008.txt WA 47 ms 37120 KB
009.txt AC 9 ms 15616 KB
010.txt AC 51 ms 49280 KB
011.txt AC 24 ms 32768 KB
012.txt WA 47 ms 37120 KB
013.txt AC 8 ms 13568 KB
014.txt AC 51 ms 49280 KB
015.txt AC 14 ms 22016 KB
016.txt WA 47 ms 37120 KB
017.txt WA 37 ms 39168 KB
018.txt AC 51 ms 49280 KB
019.txt AC 26 ms 34944 KB
020.txt AC 1 ms 256 KB
021.txt AC 1 ms 256 KB
022.txt WA 45 ms 30592 KB
023.txt WA 46 ms 34944 KB
024.txt WA 48 ms 41344 KB
025.txt WA 46 ms 34944 KB
026.txt WA 48 ms 41344 KB
027.txt WA 46 ms 34944 KB
028.txt WA 48 ms 43392 KB
029.txt WA 46 ms 34944 KB
030.txt WA 48 ms 41344 KB
031.txt WA 46 ms 34944 KB
032.txt WA 48 ms 41344 KB
033.txt WA 46 ms 34944 KB
034.txt WA 48 ms 41344 KB
035.txt WA 46 ms 34944 KB
036.txt WA 48 ms 41344 KB
037.txt WA 46 ms 34944 KB
038.txt WA 48 ms 41344 KB
039.txt WA 46 ms 34944 KB
040.txt WA 48 ms 41344 KB
041.txt WA 46 ms 34944 KB
042.txt WA 48 ms 41344 KB
example0.txt AC 1 ms 256 KB
example1.txt AC 1 ms 256 KB