Submission #147933

#	Time	Username	Problem	Language	Result	Execution time	Memory
147933		neki	Wiring (IOI17_wiring)	C++14	100 / 100	84 ms	10908 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
#define maxn 100100
#define loop(i, a, b) for(int i=a;i<b;i++)
typedef long long ll;
 
using namespace std;
 
ll min(ll a, ll b) { return (a<b)? a:b;}
 
long long min_total_length (vector <int> red, vector <int> blue) {
  pair<ll, ll> com[maxn*2];ll n=red.size()+blue.size();
  loop(i, 0, red.size()) com[i]=make_pair(red[i], 1);
  loop(i, 0, blue.size()) com[i+red.size()]=make_pair(blue[i], -1);
  com[n]=make_pair(-1, 0);
  sort(com, com+n+1);sort(red.begin(), red.end());sort(blue.begin(), blue.end());
  ll dp[maxn*2], nek[maxn*2], ind[maxn*2], bal=maxn, dif=0;loop(i, 0, 2*maxn) nek[i]=LLONG_MAX/2;dp[0]=0, nek[maxn]=0;
  loop(i, 1, n+1){
    ll ma=LLONG_MAX/2;
    bal+=com[i].second;dif+=com[i].first * com[i].second;
    if(com[i].second==1){
      auto cl=lower_bound(blue.begin(), blue.end(), com[i].first);
      if(cl!=blue.end()) ma=min(ma, (*cl)-com[i].first);
      if(cl!=blue.begin()) ma=min(ma, com[i].first-(*prev(cl)));
    }
    else{
      auto cl=lower_bound(red.begin(), red.end(), com[i].first);
      if(cl!=red.end()) ma=min(ma, (*cl)-com[i].first);
      if(cl!=red.begin()) ma=min(ma, com[i].first-(*prev(cl)));
    }
    dp[i]=min(dp[i-1]+ma, abs(dif-nek[bal])+dp[ind[bal]]);
    nek[bal]=dif;ind[bal]=i;
  }
  return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:4:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define loop(i, a, b) for(int i=a;i<b;i++)
wiring.cpp:13:8:
   loop(i, 0, red.size()) com[i]=make_pair(red[i], 1);
        ~~~~~~~~~~~~~~~~             
wiring.cpp:13:3: note: in expansion of macro 'loop'
   loop(i, 0, red.size()) com[i]=make_pair(red[i], 1);
   ^~~~
wiring.cpp:4:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define loop(i, a, b) for(int i=a;i<b;i++)
wiring.cpp:14:8:
   loop(i, 0, blue.size()) com[i+red.size()]=make_pair(blue[i], -1);
        ~~~~~~~~~~~~~~~~~            
wiring.cpp:14:3: note: in expansion of macro 'loop'
   loop(i, 0, blue.size()) com[i+red.size()]=make_pair(blue[i], -1);
   ^~~~

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