Submission #101965

#	Time	Username	Problem	Language	Result	Execution time	Memory
101965		daniel920712	전선 연결 (IOI17_wiring)	C++14	0 / 100	24 ms	1664 KiB

wiring

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <utility>
#include <vector>
#include "wiring.h"

using namespace std;
map < pair < int ,int > , long long > DP;
long long F(int N,int M,vector < int > &r,vector < int > &b)
{
    if(N==0&&M==0) return abs(r[N]-b[M]);
    else
    {
        if(DP.find(make_pair(N,M))!=DP.end()) return DP[make_pair(N,M)];
        long long t=abs(r[N]-b[M]),x=1e18;
        if(N) x=min(x,F(N-1,M,r,b));
        if(M) x=min(x,F(N,M-1,r,b));
        if(N&&M) x=min(x,F(N-1,M-1,r,b));
        //printf("%d %d %lld\n",N,M,t+x);
        DP[make_pair(N,M)]=t+x;
        return t+x;
    }
}
long long min_total_length(vector < int > r, vector < int > b)
{
    int N=r.size();
    int M=b.size();
    int i;
    long long ans=0;
    if(N<=200&&M<=200) return F(N,M,r,b);
    if(N<M)
    {
        for(i=0;i<N;i++) ans+=abs(r[i]-b[i]);
        for(i=N;i<M;i++) ans+=abs(r[N-1]-b[i]);
    }
    else
    {
        for(i=0;i<M;i++) ans+=abs(r[i]-b[i]);
        for(i=M;i<N;i++) ans+=abs(r[i]-b[0]);
    }
    return ans;
}

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