제출 #757108

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

wiring

#include<bits/stdc++.h>
#define MAXN 1007
using namespace std;

const long long inf=1e15;

int n,m;
int red[MAXN],blue[MAXN];

bool li[MAXN][MAXN];
long long dp[MAXN][MAXN];

long long ff(int l,int r){
    if(l==n and r==m)return abs(red[l]-blue[r]);

    if(li[l][r])return dp[l][r];
    li[l][r]=true;
    dp[l][r]=inf;

    if(l<n)dp[l][r]=min(dp[l][r],ff(l+1,r));
    if(r<m)dp[l][r]=min(dp[l][r],ff(l,r+1));
    if(l<n and r<m)dp[l][r]=min(dp[l][r],ff(l+1,r+1));

    dp[l][r]+=abs(red[l]-blue[r]);

    return dp[l][r];
}

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

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

    for(int i=1;i<=n;i++)red[i]=R[i-1];
    for(int i=1;i<=m;i++)blue[i]=B[i-1];

    return ff(1,1);
}

/*
int main(){
    cout<<min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10})<<"\n";
}
*/

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