제출 #68250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68250		MKopchev	전선 연결 (IOI17_wiring)	C++14	7 / 100	43 ms	4036 KiB

wiring

#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;
}
*/

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