Submission #122798

#	Time	Username	Problem	Language	Result	Execution time	Memory
122798		IOrtroiii	Wiring (IOI17_wiring)	C++14	100 / 100	101 ms	16908 KiB

wiring

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll inf = 1e18;

ll min_total_length(vector<int> r, vector<int> b) {
   vector<pair<int, int>> vals;
   for (int v : r) {
      vals.emplace_back(v, 0);
   }
   for (int v : b) {
      vals.emplace_back(v, 1);
   }
   sort(vals.begin(), vals.end());
   vector<vector<int>> sub;
   vector<vector<ll>> pref;
   vector<vector<ll>> f;
   int l = 0;
   while (l < vals.size()) {
      vector<int> csub;
      int r = l;
      while (r < vals.size() && vals[r].second == vals[l].second) {
         csub.push_back(vals[r++].first);
      }
      int sz = csub.size();
      vector<ll> cpref(sz + 1);
      for (int i = 0; i < sz; ++i) {
         cpref[i + 1] = cpref[i] + csub[i];
      }
      vector<ll> cf(sz + 1, inf);
      sub.push_back(csub);
      pref.push_back(cpref);
      f.push_back(cf);
      l = r;
   }
   int n = sub.size();
   f[0][0] = 0;
   for (int i = 0; i < n; ++i) {
      int sz = sub[i].size();
      for (int j = 0; j < sz; ++j) {
         if (i > 0) {
            f[i][j + 1] = min(f[i][j + 1], f[i][j] + sub[i][j] - sub[i - 1].back());
         }
         if (i + 1 < n) {
            f[i][j + 1] = min(f[i][j + 1], f[i][j] + sub[i + 1].front() - sub[i][j]);
            if (sz - j <= sub[i + 1].size()) {
               f[i + 1][sz - j] = min(f[i + 1][sz - j], f[i][j] + pref[i + 1][sz - j] - pref[i][sz] + pref[i][j]);
            }
         }
      }
      if (i + 1 < n) {
         f[i + 1][0] = f[i].back();
      }
   }
   return f.back().back();
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:21:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (l < vals.size()) {
           ~~^~~~~~~~~~~~~
wiring.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (r < vals.size() && vals[r].second == vals[l].second) {
              ~~^~~~~~~~~~~~~
wiring.cpp:48:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (sz - j <= sub[i + 1].size()) {
                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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