Submission #590652

#	Time	Username	Problem	Language	Result	Execution time	Memory
590652		keta_tsimakuridze	Wiring (IOI17_wiring)	C++17	100 / 100	61 ms	10848 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
#define ll long long
/*

4 5
1 2 3 7
0  4 5 9 10
*/
const ll inf = 1e18 + 5;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector<pii> x;
	x.push_back({0, -1});
	for(int i = 0; i < r.size(); i++) {
        x.push_back({r[i], 1});
	}
	for(int i = 0; i < b.size(); i++) {
        x.push_back({b[i], 0});
    }
    sort(x.begin(), x.end());
    vector<ll> dp(x.size()), suf(x.size()), pref(x.size());
    vector<int> st(x.size());
    for(int i = 1; i < x.size(); i++) {
        if(x[i].s == x[i - 1].s) st[i] = st[i - 1];
        else st[i] = i;
        dp[i] = inf;
    }
    for(int i = 1; i < x.size(); i++) {
        int j = i - 1;
        while(j + 1 < x.size() && x[i].s == x[j + 1].s) ++j;
        ll sum = 0;
        if(i != 1) {
            for(int k = i; k <= j; k++) {
                // k - i + 1
                int n = k - i + 1;
                // (max(st[i - 1], i - n), i - 1)
                sum += x[k].f - x[i].f;
                dp[k] = suf[max(st[i - 1], i - n)] + sum + (ll)(x[i].f - x[i - 1].f) * n;
                // st[i - 1] .. suf[i]
                if(i - n >= st[i - 1])
                dp[k] = min(dp[k], pref[i - n] + sum);


            }
        }
        if(j + 1 == x.size()) return dp[j];
        sum = 0;
        for(int k = j; k >= i; k--) {
            sum += x[j].f - x[k].f ;
            suf[k] = min(dp[k], dp[k - 1]) + sum;
            if(k != j)
            suf[k] = min(suf[k + 1], suf[k]);
            pref[k] = (ll)(j - k + 1) * (x[j + 1].f - x[j].f) + min(dp[k], dp[k - 1]) + sum;
        }
        for(int k = i + 1; k <= j; k++) {
            pref[k] = min(pref[k], pref[k - 1]);
        }
        i = j;
    }
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0; i < r.size(); i++) {
      |                 ~~^~~~~~~~~~
wiring.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0; i < b.size(); i++) {
      |                 ~~^~~~~~~~~~
wiring.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 1; i < x.size(); i++) {
      |                    ~~^~~~~~~~~~
wiring.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 1; i < x.size(); i++) {
      |                    ~~^~~~~~~~~~
wiring.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while(j + 1 < x.size() && x[i].s == x[j + 1].s) ++j;
      |               ~~~~~~^~~~~~~~~~
wiring.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if(j + 1 == x.size()) return dp[j];
      |            ~~~~~~^~~~~~~~~~~
wiring.cpp:16:14: warning: control reaches end of non-void function [-Wreturn-type]
   16 |  vector<pii> x;
      |              ^

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