제출 #136566

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
136566		CaroLinda	전선 연결 (IOI17_wiring)	C++14	0 / 100	29 ms	4472 KiB

wiring

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int MAXN = 100005 ;
const int MAXparcial = 210 ;
const ll inf = 1e17+10 ;
const int intinf = 1e9+100 ;

using namespace std ;

int n ,  m ;

ll r[MAXN] , b[MAXN] ;

// -------------------------------

ll dp[MAXparcial][MAXparcial] ;

ll calcDp(int i , int j)
{

	//printf("%d %d\n" , i , j ) ;

	if( i == n && j != m ) return inf ;
	if ( j== m && i != n ) return inf ;
	if(i==n && j == m) return 0 ;

	if( dp[i][j] != -1 ) return dp[i][j] ;

	return dp[i][j] = abs(r[i] - b[j]) + min( calcDp(i+1, j) , calcDp(i+1,j+1) ) ;

}

ll parcial()
{	
	memset(dp,-1,sizeof dp) ;

	if( m > n )
	{

		vector<ll> aux ;

		lp(i,0,m) aux.pb( b[i] ) ;

		lp(i,0,n) b[i] = r[i] ;

		lp(i,0,m) r[i] = aux[i] ;

		swap(n,m) ;

	}

	b[m] = intinf ;

	return calcDp(0,0) ;

}

ll min_total_length( vector<int> R , vector<int> B )
{

	n = R.size() , m = B.size() ;

	lp(i,0,n) r[i] = R[i] ;
	lp(i,0,m) b[i] = B[i] ;

	return parcial() ;

}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45