제출 #249885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
249885		fedoseevtimofey	전선 연결 (IOI17_wiring)	C++14	100 / 100	71 ms	9860 KiB

wiring

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

#include "wiring.h"

const ll Inf = 1e18;

long long min_total_length(vector <int> r, vector <int> b) {
  int n = r.size();
  int m = b.size();
  vector <pair <int, int>> gs;
  for (int i = 0; i < n; ++i) {
    gs.push_back({r[i], 0});
  }
  for (int i = 0; i < m; ++i) {
    gs.push_back({b[i], 1});
  }
  sort(gs.begin(), gs.end());
  int k = gs.size();
  vector <int> g_sz;

  for (int i = 0; i < k; ++i) {
    int uk = i;
    while (uk < k && gs[i].second == gs[uk].second) {
      ++uk;
    }
    g_sz.push_back(uk - i);
    i = uk - 1;
  }
  int cnt = g_sz.size();

  vector <int> where(k); 
  {
    int uk = 0;
    for (int i = 0; i < cnt; ++i) {
      for (int j = uk; j < uk + g_sz[i]; ++j) {
        where[j] = i;
      }
      uk += g_sz[i];
    }
  }
  vector <int> ps(cnt);
  for (int i = 0; i < cnt; ++i) {
    if (i > 0) ps[i] += ps[i - 1];
    ps[i] += g_sz[i];
  }
  vector <ll> pref(k + 1);

  for (int i = 0; i < k; ++i) {
    pref[i + 1] = pref[i] + gs[i].first;
  }

  vector <ll> dp(k + 1, Inf);
  dp[0] = 0;
  for (int i = 1; i <= k; ++i) {
    int id = where[i - 1];
    if (id > 0) {
      dp[i] = min(dp[i], dp[i - 1] + abs(gs[i - 1].first - gs[ps[id - 1] - 1].first));
    }
    if (id + 1 < cnt) {
      dp[i] = min(dp[i], dp[i - 1] + abs(gs[i - 1].first - gs[ps[id]].first));
    }
    if (id + 1 < cnt) {
      int have_free = ps[id] - i + 1;
      if (g_sz[id + 1] >= have_free) {
        ll delta = 0;
        delta += pref[ps[id] + have_free] - pref[ps[id]];
        delta -= pref[i - 1 + have_free] - pref[i - 1];
        /*for (int j = 0; j < have_free; ++j) {
          delta += abs(gs[i - 1 + j].first - gs[ps[id] + j].first);
        }*/
        dp[ps[id] + have_free] = min(dp[ps[id] + have_free], dp[i - 1] + delta);
      }
    }
  }   
  return dp[k];
}

#ifdef LOCAL
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, m;
	cin >> n >> m;
	vector<int> r(n), b(m);
	for(int i = 0; i < n; i++)
    cin >> r[i];
	for(int i = 0; i < m; i++)
    cin >> b[i];
	long long res = min_total_length(r, b);
  cout << res << '\n';
}
#endif

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