Submission #311145

#	Time	Username	Problem	Language	Result	Execution time	Memory
311145		quocnguyen1012	Wiring (IOI17_wiring)	C++14	100 / 100	122 ms	34536 KiB

wiring

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5;

vector<int> seg[maxn];
vector<ll> last[maxn], first[maxn], f[maxn];
int N;

long long min_total_length(vector<int> r,vector<int> b) {
  vector<ii> coor;
  for (auto & it : r) {
    coor.eb(it, 0);
  }
  for (auto & it : b) {
    coor.eb(it, 1);
  }
  sort(coor.begin(), coor.end());

  int now = -1;
  seg[0].pb(-1e9);
  for (auto & it : coor) {
    if (it.se == now) {
      seg[N].eb(it.fi);
    } else {
      ++N;
      seg[N].eb(-1e9);
      seg[N].eb(it.fi);
      now = it.se;
    }
  }

  for (int i = 0; i <= N; ++i) {
    int sz = seg[i].size();
    last[i].assign(sz, 0);
    first[i].assign(sz, 0);
    f[i].assign(sz, 1e18);

    for (int j = 1; j < sz; ++j) {
      first[i][j] = first[i][j - 1] + seg[i][j];
      last[i][j] = last[i][j - 1] + seg[i][sz - j];
    }
  }

  f[0][0] = 0;
  for (int i = 0; i < N; ++i) {
    int nowsz = seg[i].size() - 1, nxtsz = seg[i + 1].size() - 1;
    for (int j = nowsz; j > 0; --j) {
      f[i][j - 1] = min(f[i][j - 1], f[i][j] + seg[i + 1][1] - seg[i][nowsz - j + 1]);
    }
    for (int j = 0; j <= min(nowsz, nxtsz); ++j) {
      f[i + 1][nxtsz - j] = min(f[i + 1][nxtsz - j], f[i][j] + first[i + 1][j] - last[i][j]);
    }
    for (int j = nxtsz; j > 0; --j) {
      if (i != 0)
        f[i + 1][j - 1] = min(f[i + 1][j - 1], f[i + 1][j] + seg[i + 1][nxtsz - j + 1] - seg[i][nowsz]);
    }
  }
  return f[N][0];
}

#ifdef LOCAL
signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
  freopen("A.INP", "r", stdin);
  freopen("A.OUT", "w", stdout);
#endif // LOCAL
  int n, m; cin >> n >> m;
  vector<int> r(n), b(m);
  for (auto & it : r) cin >> it;
  for (auto & it : b) cin >> it;
  cout << min_total_length(r, b);
}
#endif

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