Submission #68692

#	Time	Username	Problem	Language	Result	Execution time	Memory
68692		Talant	Wiring (IOI17_wiring)	C++17	100 / 100	97 ms	77948 KiB

wiring

#include "wiring.h"
//#include "grader.cpp"

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb push_back

using namespace std;

const int N = (1e6 + 5);
const long long inf = (1e18 + 7);

long long n,m;
long long id = 0;
long long pr[N];
long long dp[N];

pair<long long,long long> a[N];
vector <pair<long long,long long> > v;

long long min_total_length(vector<int> r, vector<int> b) {
      n = r.size();
      m = b.size();

      v.pb(mk(-inf,-1));
      for (int i = 0; i < r.size(); i ++) v.pb(mk(r[i],0));
      for (int i = 0; i < b.size(); i ++) v.pb(mk(b[i],1));

      sort (v.begin(),v.end());

      for (int i = 1; i < v.size(); i ++)
            pr[i] = pr[i - 1] + v[i].fr;

      for (int i = 1; i < v.size(); i ++) {
            int j = i + 1;
            while (j < v.size() && v[j].sc == v[i].sc)
                   ++j;
            a[++id] = mk(i,j - 1);
            i = j - 1;
      }

      for (int i = a[1].fr; i <= a[1].sc; i ++)
            dp[i] = i * v[a[2].fr].fr - pr[i];

      for (int i = 2; i <= id; i ++) {
            long long l1 = a[i - 1].fr;
            long long r1 = a[i - 1].sc;
            long long l2 = a[i].fr;
            long long r2 = a[i].sc;

            for (int j = l2; j <= r2; j ++) {
                  dp[j] = inf;
                  if ((j - l2 + 1) <= (r1 - l1 + 1))
                        dp[j] = dp[r1 - (j - l2 + 1)] + (pr[j] - pr[l2 - 1]) - (pr[r1] - pr[r1 - (j - l2 + 1)]);
                  if (i + 1 <= id)
                        dp[j] = min(dp[j],dp[j - 1] + v[a[i + 1].fr].fr - v[j].fr);
                  dp[j] = min(dp[j],dp[j - 1] + v[j].fr - v[r1].fr);
            }
      }
      return dp[n + m];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:29:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < r.size(); i ++) v.pb(mk(r[i],0));
                       ~~^~~~~~~~~~
wiring.cpp:30:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < b.size(); i ++) v.pb(mk(b[i],1));
                       ~~^~~~~~~~~~
wiring.cpp:34:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 1; i < v.size(); i ++)
                       ~~^~~~~~~~~~
wiring.cpp:37:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 1; i < v.size(); i ++) {
                       ~~^~~~~~~~~~
wiring.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (j < v.size() && v[j].sc == v[i].sc)
                    ~~^~~~~~~~~~

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