Submission #172324

#	Time	Username	Problem	Language	Result	Execution time	Memory
172324		AlexLuchianov	Wiring (IOI17_wiring)	C++14	100 / 100	66 ms	9064 KiB

wiring

#include "wiring.h"
#include <vector>
#include <algorithm>
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 2e5;
int const coordmax = 1e9;
ll const inf = 1LL * coordmax * coordmax;

struct Wire{
  int color;
  int dist;
  bool operator < (Wire const &a) const{
    return dist < a.dist;
  }
};

std::vector<Wire> v;
ll dp[1 + nmax], sum[1 + nmax];
std::vector<int> changes;

ll getsum(int x, int y){
  if(x == 0)
    return sum[y];
  else
    return sum[y] - sum[x - 1];
}


long long min_total_length(std::vector<int> r, std::vector<int> b) {
  int n = r.size() + b.size();
  v.push_back({0, -1}); ///just for filling the empty space
  for(int i = 0; i < r.size(); i++)
    v.push_back({1, r[i]});
  for(int i = 0; i < b.size(); i++)
    v.push_back({2, b[i]});
  v.push_back({0, coordmax + 1});

  std::sort(v.begin(), v.end());
  for(int i = 1; i <= n; i++)
    sum[i] = sum[i - 1] + v[i].dist;
  for(int i = 1; i <= n; i++)
    if(v[i - 1].color != v[i].color)
      changes.push_back(i);
  changes.push_back(n + 1);
  for(int i = 1; i <= n; i++)
    dp[i] = inf;
  dp[0] = 0;

  for(int group = 1; group < changes.size() - 1; group++){
    int x = changes[group], y = changes[group + 1] - 1, lim = changes[group - 1];
    ll result = inf;
    for(int i = y; x <= i; i--){
      if(i < y)
        result = result - v[i + 1].dist + v[x].dist;

      int x2 = x - 1 - (i - x);
      if(lim <= x2) {
        result = MIN(result, MIN(dp[x2], dp[x2 - 1]) + getsum(x, i) - getsum(x2, x - 1));
        ll adaos = 0;
        while(i == y && lim <= x2){
          result = MIN(result, MIN(dp[x2], dp[x2 - 1]) + getsum(x, i) - getsum(x2, x - 1) + adaos);
          x2--;
          adaos += v[x].dist;
        }
      }
      dp[i] = MIN(dp[i], result);
    }
    result = inf;
    for(int i = x; i <= y; i++){
      result = result + v[i].dist - v[x - 1].dist;
      int x2 = x - 1 - (i - x);
      if(lim <= x2)
        result = MIN(result, MIN(dp[x2], dp[x2 - 1]) + getsum(x, i) - getsum(x2, x - 1));
      dp[i] = MIN(dp[i], result);
    }
    /*
    std::cout << group << " " << x << " " << y << '\n';
    for(int i = x; i <= y; i++)
      std::cout << dp[i] << " ";
    std::cout << '\n' << '\n';
    //*/

  }
  return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < r.size(); i++)
                  ~~^~~~~~~~~~
wiring.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < b.size(); i++)
                  ~~^~~~~~~~~~
wiring.cpp:54:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int group = 1; group < changes.size() - 1; group++){
                      ~~~~~~^~~~~~~~~~~~~~~~~~~~

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