Submission #206568

#	Time	Username	Problem	Language	Result	Execution time	Memory
206568		impetus_	전선 연결 (IOI17_wiring)	C++14	0 / 100	14 ms	12152 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forev(i, a, b) for(int i = a; i >= b; i--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int maxn = (int)1e6 + 100;
const int mod = (int)1e9 + 7;
const int inf = (int)1e9;
const double pi = acos(-1.0);

int n, m, a, b, go[maxn], was[2], cnt[maxn], used[maxn + maxn], K = 500000;
ll dp[maxn], s[maxn];
vpii v;
ll min_total_length(vi v1, vi v2) {
  n = sz(v1), m = sz(v2);
  for(auto a : v1) v.pb(mp(a, 0));
  for(auto b : v2) v.pb(mp(b, 1));
  sort(all(v));
  forn(i, 0, maxn - 1) go[i] = inf;
  was[0] = was[1] = -1; 
  int i = 0;
  for(auto x : v){
    i++;
    if(was[!x.s] != -1) go[i] = x.f - was[!x.s];
    was[x.s] = x.f;
    if(x.s) cnt[i] = 1, s[i] = x.f;
    else cnt[i] = -1, s[i] = -x.f;
    cnt[i] += cnt[i - 1];
    s[i] += s[i - 1];
  }
  was[0] = was[1] = -1; i = n + 1;
  reverse(all(v));
  for(auto x : v){
    i--;
    if(was[!x.s] != -1) go[i] = min(go[i], was[!x.s] - x.f);
    was[x.s] = x.f;
  }
  memset(used, -1, sizeof(used));
  used[K] = 0;
  forn(i, 1, n + m){
    dp[i] = dp[i - 1] + go[i];
    if(used[cnt[i] + K] != -1){
      int j = used[cnt[i] + K] + 1;
      dp[i] = min(dp[i], dp[j - 1] + abs(s[i] - s[j - 1]));
    }
    used[cnt[i] + K] = i;
  }
  return dp[n + m];
}/*
int main () {
  int t = 1;
  //scanf("%d", &t);
  while(t--) solve();
}

// to check runtime errors
// special case


*/

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