Submission #68608

#	Time	Username	Problem	Language	Result	Execution time	Memory
68608		Talant	Wiring (IOI17_wiring)	C++17	0 / 100	2 ms	524 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);
const long long M = (1e10 + 7);

long long dp[N];
long long lastr,lastb;
long long cn[N];

vector <pair<long long,long long> > vec;
deque <int> red,blue;

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

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

      for (int i = 0; i < b.size(); i ++)
            vec.pb(mk(b[i],1));

      sort (vec.begin(),vec.end());
      for (int i = 1; i <= n + m; i ++) dp[i] = inf;

      dp[0] = 0;
      lastr = lastb = -1;

      for (int i = 1; i <= n + m; i ++) {
            long long val = vec[i].fr,tp = vec[i].sc;
            long long sum = 0;
            if (tp == 0) {
                  if (i == 1) {
                        dp[i] = M;
                        lastr = i;
                        continue;
                  }
                  if (lastr == i - 1) {
                        if (cn[i - 1] >= 1) dp[i] = min(dp[i],dp[i - 1] + abs(val - vec[i - 1].fr)),cn[i] = max(0ll,cn[i - 1] - 1);
                        else {
                              if (lastb != -1) {
                                    dp[i] = min(dp[i],dp[i - 1] + abs(val - vec[lastb].fr));
                              }
                              else dp[i] = M;
                        }
                  }
                  else {
                        for (int j = i - 1; j >= 1; j --) {
                              if (vec[j].sc == 0) break;
                              sum += vec[j].fr;
                              if (dp[i] >= dp[j - 1] + abs(val * (i - j) - sum))
                                    dp[i] = dp[j - 1] + abs(val * (i - j) - sum),cn[i] ++;
                              else break;
                        }
                        cn[i] --;
                        if (dp[i] > dp[i - 1] + abs(val - vec[i - 1].fr))
                              dp[i] = min(dp[i],dp[i - 1] + abs(val - vec[i - 1].fr)),cn[i] = 0;
                  }
                  lastr = i;
            }
            else {
                  if (i == 1) {
                        dp[i] = M;
                        lastb = i;
                        continue;
                  }
                  if (lastb == i - 1) {
                        if (cn[i - 1] >= 1) dp[i] = min(dp[i],dp[i - 1] + abs(val - vec[i - 1].fr)),cn[i] = max(0ll,cn[i - 1] - 1);
                        else {
                              if (lastr != -1) {

                                    dp[i] = min(dp[i],dp[i - 1] + abs(val - vec[lastr].fr));

                              }
                              else dp[i] = M;
                        }
                  }
                  else {
                        for (int j = i - 1; j >= 1; j --) {
                              if (vec[j].sc == 1) break;
                              sum += vec[j].fr;
                              if (dp[i] >= dp[j - 1] + abs(val * (i - j) - sum))
                                    dp[i] = dp[j - 1] + abs(val * (i - j) - sum),cn[i] ++;
                              else break;

                        }
                        cn[i] --;
                        if (dp[i] > dp[i - 1] + abs(val - vec[i - 1].fr))
                              dp[i] = min(dp[i],dp[i - 1] + abs(val - vec[i - 1].fr)),cn[i] = 0;
                  }
                  lastb = i;
            }
            cn[i] = max(0ll,cn[i]);
      }
      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 ++)
                       ~~^~~~~~~~~~
wiring.cpp:32:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < b.size(); i ++)
                       ~~^~~~~~~~~~

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