제출 #640440

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

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
 
int R[200002],B[200002];
int n,m;
lint D[202][202];

lint f(int p,int q)
{
  if(D[p][q]>=0)return D[p][q];
  if(p==0 && q==0)return D[p][q]=0;
  if(p==0 || q==0)return D[p][q]=1e18;
  lint sum=0;
  D[p][q]=1e18;
  for(int i=q;i>=1;i--)
  {
    sum+=abs(R[p]-B[i]);
    D[p][q]=min(D[p][q],sum+f(p-1,i-1));
  }

  sum=0;
  for(int i=p;i>=1;i--)
  {
    sum+=abs(R[i]-B[q]);
    D[p][q]=min(D[p][q],sum+f(i-1,q-1));
  }
  return D[p][q];
}
lint min_total_length(vector<int> r, vector<int> b) {
  lint ans=0;
  n=sz(r),m=sz(b);
  for(int i=0;i<n;i++)R[i+1]=r[i];
  for(int j=0;j<m;j++)B[j+1]=b[j];
  memset(D,-1,sizeof(D));
  ans=f(n,m);
	return ans;
}

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