Submission #644946

#	Time	Username	Problem	Language	Result	Execution time	Memory
644946		slime	Wiring (IOI17_wiring)	C++14	0 / 100	1 ms	212 KiB

wiring

#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e5 + 10;
long long ps[MAXN];
long long f(int l1, int r1, int l2, int r2) {
  long long cntB = r2 - l2 + 1;
  long long cntR = r1 - l1 + 1;
  if(cntR == 1) {
    long long sumB = ps[r2] - ps[l2 - 1];
    return sumB - cntB * (ps[r1] - ps[r1 - 1]);
  }
  if(cntB == 1) {
    long long sumR = ps[r1] - ps[l1 - 1];
    return (ps[l2] - ps[l2 - 1]) * cntR - sumR;
  }
  long long sumB = ps[r2] - ps[l2];
  long long sumR = ps[r1 - 1] - ps[l1 - 1];
  return sumB - (cntB - 1) * (ps[r1] - ps[r1 - 1]) + (cntR - 1) * (ps[l2] - ps[l2 - 1]) - sumR;
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
  vector<pair<long long, char> > all;
  all.push_back({-1, 'N'});
  for(int i=0; i<r.size(); i++) all.push_back({r[i], 'R'});
  for(int i=0; i<b.size(); i++) all.push_back({b[i], 'B'});
  sort(all.begin(), all.end());
  int n = all.size() - 1;
  long long dp[n+1];
  ps[0] = 0;
  for(int i=1; i<=n; i++) ps[i] = ps[i-1] + all[i].first;

  return f(1, r.size(), r.size() + 1, n);

  dp[0] = 0;
  for(int i=1; i<=n; i++) {
    dp[i] = 1e18;
    bool active = 0;
    int cntsame = 0, cntdiff = 0;
    for(int j=i; j>=1; j--) {
      if(all[j].second == all[i].second && active) {
        break;
      }
      if(all[j].second == all[i].second) cntsame++;
      if(all[j].second != all[i].second) {
        active = 1; // use [j, i], reference dp[j-1]
        cntdiff++;
        dp[i] = min(dp[i], dp[j-1] + f(j, j+cntdiff-1, j+cntdiff, i));
      }
    }
  }
  return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int i=0; i<r.size(); i++) all.push_back({r[i], 'R'});
      |                ~^~~~~~~~~
wiring.cpp:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i=0; i<b.size(); i++) all.push_back({b[i], 'B'});
      |                ~^~~~~~~~~

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