제출 #420930

#제출 시각아이디문제언어결과실행 시간메모리
420930MDario전선 연결 (IOI17_wiring)C++11
7 / 100
153 ms262148 KiB
#include "wiring.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; #define F first #define S second long long min_total_length(vector<int> r, vector<int> b) { ll n=r.size(), m=b.size(); if(r.back()<b[0]){ ll c=0, c1=0; for(int i=0; i<n; i++)c+=r[i]; for(int i=0; i<m; i++)c1+=b[i]; if(n>m){ return c1-c-(n-m)*r.back(); } else{ return c1-c+(m-n)*b[0]; } } ll dp[n+1][m+1]; dp[0][0]=abs(r[0]-b[0]); for(int i=0; i<n; i++){ for(int t=0; t<m; t++){ if(i==0&&t==0)continue; else if(i==0){ dp[i][t]=abs(r[i]-b[t])+dp[i][t-1]; } else if(t==0){ dp[i][t]=abs(r[i]-b[t])+dp[i-1][t]; } else{ dp[i][t]=abs(r[i]-b[t])+min(dp[i-1][t-1], min(dp[i-1][t], dp[i][t-1])); } } } 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...