제출 #1115360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115360		epicci23	전선 연결 (IOI17_wiring)	C++17	7 / 100	252 ms	262144 KiB

wiring

#include "bits/stdc++.h"
#include "wiring.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;

const ll INF = 1e18;

ll min_total_length(vector<int> R, vector<int> B){
  ll n = sz(R), m = sz(B);
  
  ll ar[n+5],ar2[m+5];
  for(ll i=0;i<n;i++) ar[i] = R[i];
  for(ll i=0;i<m;i++) ar2[i] = B[i];

  array<ll,2> range[n+5];
  for(ll i=0;i<n;i++){
    ll l = lower_bound(ar2,ar2+m,(i>0 ? ar[i-1] : -1)) - ar2;
    ll r = lower_bound(ar2,ar2+m,(i+1<n ? ar[i+1] : INF)) - ar2;
    l = max(0LL, l - 1);
    r = min(m-1, r + 1);
    range[i][0] = l;
    range[i][1] = r;
  }

  ll dp[n+5][m+5];
  for(int i=0;i<n;i++){
  	for(int j=0;j<m;j++){
  	 ll cur = INF;
  	 if(i==0 && j==0) cur = 0;
  	 if(i && j)cur = min(cur, dp[i-1][j-1]);
     if(j) cur = min(cur, dp[i][j-1]);
     if(i) cur = min(cur, dp[i-1][j]);
     dp[i][j] = cur + abs(ar[i] - ar2[j]);
  	}
  }

  return dp[n-1][m-1];
}



/*void _(){
  ll n,m;
  cin >> n >> m;
  ll ar[n+5],ar2[m+5];
  for(ll i=0;i<n;i++) cin >> ar[i];
  for(ll i=0;i<m;i++) cin >> ar2[i];

  array<ll,2> range[n+5];
  for(ll i=0;i<n;i++){
    ll l = lower_bound(ar2,ar2+m,(i>0 ? ar[i-1] : -1)) - ar2;
    ll r = lower_bound(ar2,ar2+m,(i+1<m ? ar[i+1] : INF)) - ar2;
    l--;
    r++;
    l = max(0LL, l);
    r = min(m-1, r);
    range[i][0] = l;
    range[i][1] = r;
  }

  ll dp[n+5][m+5];
  for(int i=0;i<n;i++){
  	for(int j=0;j<m;j++){
  	 ll cur = INF;
  	 if(i==0 && j==0) cur = 0;
  	 if(i && j)cur = min(cur, dp[i-1][j-1]);
     if(j) cur = min(cur, dp[i][j-1]);
     if(i) cur = min(cur, dp[i-1][j]);
     dp[i][j] = cur + abs(ar[i] - ar2[j]);
  	}
  }

  cout << dp[n-1][m-1] << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  ll tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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