제출 #68250

#제출 시각아이디문제언어결과실행 시간메모리
68250MKopchev전선 연결 (IOI17_wiring)C++14
7 / 100
43 ms4036 KiB
#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
const int nmax=2e2+42;
long long dp[nmax][nmax];
long long min_total_length(vector<int> r, vector<int> b)
{
    int n=r.size(),m=b.size();
    assert(n<nmax&&m<nmax);
    long long now;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
        if(i==0&&j==0){dp[i][j]=abs(r[i]-b[j]);continue;}
        now=1e18;
        if(i)now=min(now,dp[i-1][j]+abs(r[i]-b[j]));
        if(j)now=min(now,dp[i][j-1]+abs(r[i]-b[j]));
        if(i&&j)now=min(now,dp[i-1][j-1]+abs(r[i]-b[j]));
        dp[i][j]=now;
        }
    return dp[n-1][m-1];
}
/*
int main()
{
    cout<<min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10})<<endl;
}
*/
#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...