제출 #1300991

#제출 시각아이디문제언어결과실행 시간메모리
1300991thelegendary08전선 연결 (IOI17_wiring)C++17
7 / 100
164 ms327680 KiB
#include "wiring.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
const int mxn = 1e5 + 5;
using namespace std;
vi a, b; 
int dist(int i, int j){
	return abs(a[i] - b[j]); 
}
long long min_total_length(std::vector<signed> R, std::vector<signed> B) {
	int n = R.size(); int m = B.size();
	a.resize(n), b.resize(m); f0r(i,n)a[i]=R[i]; f0r(i,m)b[i]=B[i];
	vvi dp(n, vi(m,4e18)); int sum = 0; f0r(i,m){sum += dist(0,i); dp[0][i] = sum;}
	FOR(i,1,n){
		f0r(j,m){
			dp[i][j] = min(dp[i][j], dp[i-1][j] + dist(i,j)); int cur = 0; 
			for(int k = j; k > 0; k--)cur += dist(i, k), dp[i][j] = min(dp[i][j], dp[i-1][k-1] + cur); 
		}
	} return dp[n-1][m-1]; 
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...