Submission #1115279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115279		epicci23	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	508 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<m ? ar[i+1] : INF)) - ar2;
    l = max(0LL, l - 1);
    r = min(m-1, r + 1);
    range[i][0] = l;
    range[i][1] = r;
  }

  vector<ll> dp(m+5, INF);
  for(ll i=0;i<n;i++){
  	map<ll, ll> ndp;
    for(ll j=range[i][0];j<=range[i][1];j++){
      ll curi = INF;
      if(i==0 || j==0) curi = 0;
      if(j>0) curi = min(curi, dp[j-1]);
      curi = min(curi, dp[j]);
      if(ndp.count(j-1)) curi=min(curi, ndp[j-1]);

      if(ndp.count(j)) ndp[j] = min(ndp[j], curi + abs(ar[i] - ar2[j]));
      else ndp[j] = curi + abs(ar[i] - ar2[j]);
    }
    for(auto x:ndp) dp[x.first] = x.second;
  }

  return dp[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;
  }

  vector<ll> dp(m+5, INF);
  for(ll i=0;i<n;i++){
  	map<ll, ll> ndp;
    for(ll j=range[i][0];j<=range[i][1];j++){
      ll curi = INF;
      if(i==0 || j==0) curi = 0;
      if(j>0) curi = min(curi, dp[j-1]);
      curi = min(curi, dp[j]);
      if(ndp.count(j-1)) curi=min(curi, ndp[j-1]);

      if(ndp.count(j)) ndp[j] = min(ndp[j], curi + abs(ar[i] - ar2[j]));
      else ndp[j] = curi + abs(ar[i] - ar2[j]);
    }
    for(auto x:ndp) dp[x.first] = x.second;
  }

  cout << dp[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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45