Submission #640438

#	Time	Username	Problem	Language	Result	Execution time	Memory
640438		ggoh	Wiring (IOI17_wiring)	C++14	0 / 100	20 ms	4752 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;
  if(p<q)
  {
    lint sum=0;
    D[p][q]=1e18;
    for(int i=1;i<=q-p+1;i++)
    {
      sum+=abs(R[p]-B[q-i+1]);
      D[p][q]=min(D[p][q],sum+f(p-1,q-i));
    }
  }
  else
  {
    lint sum=0;
    D[p][q]=1e18;
    for(int i=1;i<=p-q+1;i++)
    {
      sum+=abs(R[p-i+1]-B[q]);
      D[p][q]=min(D[p][q],sum+f(p-i,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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45