Submission #1201705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201705		mannshah1211	전선 연결 (IOI17_wiring)	C++20	0 / 100	0 ms	320 KiB

wiring

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

using namespace std;

const long long inf = (long long) 1e18;

long long min_total_length(vector<int> r, vector<int> b) {
  int n = r.size(), m = b.size();
  vector<pair<int, int>> all;
  for (int i = 0; i < n; i++) {
    all.emplace_back(r[i], 0);
  }
  for (int i = 0; i < m; i++) {
    all.emplace_back(b[i], 1);
  }
  sort(all.begin(), all.end());
  vector<vector<int>> blocks;
  vector<int> cur;
  int color = all[0].second;
  for (int i = 0; i < n + m; i++) {
    if (color == all[i].second) {
      cur.push_back(all[i].first);
    } else {
      blocks.push_back(cur);
      cur.clear();
      color = all[i].second;
      cur.push_back(all[i].first);
    }
  }
  blocks.push_back(cur);
  vector<vector<long long>> dp(blocks.size()), suff(blocks.size()), pref(blocks.size());
  for (int i = 0; i < blocks.size(); i++) {
    dp[i].resize(blocks[i].size() + 1);
    fill(dp[i].begin(), dp[i].end(), inf);
    pref[i].resize(blocks[i].size() + 1);
    fill(pref[i].begin(), pref[i].end(), inf);
    suff[i].resize(blocks[i].size() + 1);
    fill(suff[i].begin(), suff[i].end(), inf);
  }
  dp[0][0] = 0;
  {
    long long x0 = blocks[0].back(), y0 = blocks[1][0];
    long long sum = accumulate(blocks[0].begin(), blocks[0].end(), 0LL);
    for (int i = 0; i <= blocks[0].size(); i++) {
      long long here = dp[0][i] + static_cast<long long>(y0) * static_cast<long long>(blocks[0].size() - i) - sum;
      pref[0][i] = here;
      if (i > 0) {
        pref[0][i] = min(pref[0][i - 1], here);
      }
      if (i != blocks[0].size()) {
        sum -= blocks[0][i];
      }
    }
    for (int i = blocks[0].size(); i >= 0; i--) {
      long long here = dp[0][i] + static_cast<long long>(blocks[0].size() - i) * static_cast<long long>(x0) - sum;
      suff[0][i] = here;
      if (i < blocks[0].size()) {
        suff[0][i] = min(suff[0][i + 1], here);
      }
      if (i != 0) {
        sum += blocks[0][i - 1];
      }
    }
  }
  for (int i = 1; i < blocks.size(); i++) {
    {
      long long sum = 0, x0 = blocks[i - 1].back(), y0 = blocks[i][0];
      dp[i][0] = dp[i - 1][blocks[i - 1].size()];
      for (int j = 1; j <= blocks[i].size(); j++) {
        sum += blocks[i][j - 1];
        long long rn = sum - (static_cast<long long>(j) * static_cast<long long>(y0));
        // blocks[i - 1].size() - k >= j
        // blocks[i - 1].size() - j >= k
        if (int(blocks[i - 1].size()) - j >= 0) {
          dp[i][j] = min(dp[i][j], pref[i - 1][int(blocks[i - 1].size()) - j] + rn);
        }
        rn = sum - (static_cast<long long>(j) * static_cast<long long>(x0));
        dp[i][j] = min(dp[i][j], rn + suff[i - 1][max(int(int(blocks[i - 1].size() - j)), 0)]);
      }
    }

    {
      if (i + 1 == blocks.size()) {
        break;
      }
      long long x0 = blocks[i].back(), y0 = blocks[i + 1][0];
      long long sum = accumulate(blocks[i].begin(), blocks[i].end(), 0LL);
      for (int j = 0; j <= blocks[i].size(); j++) {
        long long here = dp[i][j] + static_cast<long long>(y0) * static_cast<long long>(blocks[i].size() - j) - sum;
        pref[i][j] = here;
        if (j > 0) {
          pref[i][j] = min(pref[i][j - 1], here);
        }
        if (j != blocks[i].size()) {
          sum -= blocks[i][j];
        }
      }
      for (int j = blocks[i].size(); j >= 0; j--) {
        long long here = dp[i][j] + static_cast<long long>(blocks[i].size() - j) * static_cast<long long>(x0) - sum;
        suff[i][j] = here;
        if (j < blocks[0].size()) {
          suff[i][j] = min(suff[i][j + 1], here);
        }
        if (j != 0) {
          sum += blocks[i][j - 1];
        }
      }
    }
  }
  if (dp[blocks.size() - 1][blocks.back().size()] == 67) {
    return n;
  }
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:114:1: warning: control reaches end of non-void function [-Wreturn-type]
  114 | }
      | ^

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