Submission #59138448

Source Code Expand

#include <bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef modint1000000007 mi;
constexpr ll mod=1000000007;
constexpr ll inf=1ll<<61;
constexpr double PI=3.1415926535897932;

ll dp[402][402];
ll a[402];

ll memo(int L,int R){
	if(dp[L][R]!=inf)return dp[L][R];
	if(L>R)return dp[L][R]=0;

	ll ans=abs(a[L]-a[R])+memo(L+1,R-1);
	for(int i=L+1;i<R;i+=2)ans=min(ans,memo(L,i)+memo(i+1,R));

	return dp[L][R]=ans;

}

int main(){
	int n;cin>>n;
	rep(i,2*n)cin>>a[i];
	rep(i,2*n)rep(j,2*n)dp[i][j]=inf;
	cout<<memo(0,2*n-1)<<endl;
	
}

Submission Info

Submission Time
Task 019 - Pick Two（★6）
User Rho17
Language C++ 20 (gcc 12.2)
Score 6
Code Size 721 Byte
Status AC
Exec Time 17 ms
Memory 4740 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 6 / 6
Status
AC × 4
AC × 14
Set Name Test Cases
Sample 00_sample_0.txt, 00_sample_1.txt, 00_sample_2.txt, 00_sample_3.txt
All 00_sample_0.txt, 00_sample_1.txt, 00_sample_2.txt, 00_sample_3.txt, 01_cornar_0.txt, 01_cornar_1.txt, 01_cornar_2.txt, 02_random_0.txt, 02_random_1.txt, 02_random_2.txt, 02_random_3.txt, 03_maxima_0.txt, 03_maxima_1.txt, 03_maxima_2.txt
Case Name Status Exec Time Memory
00_sample_0.txt AC 1 ms 3488 KiB
00_sample_1.txt AC 1 ms 3488 KiB
00_sample_2.txt AC 1 ms 3420 KiB
00_sample_3.txt AC 1 ms 3564 KiB
01_cornar_0.txt AC 1 ms 3448 KiB
01_cornar_1.txt AC 1 ms 3544 KiB
01_cornar_2.txt AC 3 ms 4104 KiB
02_random_0.txt AC 3 ms 4136 KiB
02_random_1.txt AC 1 ms 3848 KiB
02_random_2.txt AC 2 ms 3860 KiB
02_random_3.txt AC 14 ms 4656 KiB
03_maxima_0.txt AC 15 ms 4688 KiB
03_maxima_1.txt AC 17 ms 4708 KiB
03_maxima_2.txt AC 16 ms 4740 KiB