Submission #116972

#	Time	Username	Problem	Language	Result	Execution time	Memory
116972		zubec	Wiring (IOI17_wiring)	C++14	100 / 100	101 ms	11880 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[2][200100];

ll pref[200100];

int prv[200100], nxt[200100];

long long min_total_length(std::vector<int> r, std::vector<int> b) {

    vector <pair<int, int> > vec;
    for (int i = 0; i < r.size(); i++){
        vec.push_back({r[i], 0});
    }
    for (int i = 0; i < b.size(); i++){
        vec.push_back({b[i], 1});
    }
    int n = vec.size();
    sort(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++){
        if (i == 0 || vec[i].second != vec[i-1].second){
            prv[i] = i;
        } else
            prv[i] = prv[i-1];
    }
    for (int i = n-1; i >= 0; i--){
        if (i == n-1 || vec[i].second != vec[i+1].second)
            nxt[i] = i+1; else
            nxt[i] = nxt[i+1];
    }
    dp[0][0] = 0;
    dp[1][0] = 1e18;
    for (int i = 1; i <= n; i++){
        dp[0][i] = dp[1][i] = 1e18;
        pref[i] = pref[i-1] + vec[i-1].first;
        int l = prv[i-1], r = nxt[i-1];
        if (i-1 == l)
            dp[0][i] = min(dp[0][i], dp[1][i-1]);
        if (l != 0){
            dp[0][i] = min(dp[0][i], dp[0][i-1] + vec[i-1].first - vec[l-1].first);
            int len = i-l;
            if (l-len >= 0){
                dp[0][i] = min(dp[0][i], dp[0][l-len] + pref[i]-pref[l] - (pref[l]-pref[l-len]));

            }
        }
        if (r != n){
            dp[1][i] = min(dp[1][i], dp[0][i-1] + vec[r].first-vec[i-1].first);
        }
        dp[0][i] = min(dp[0][i], dp[1][i]);
    }
    return dp[0][n];


}

/**

4 5
1 2 3 7
0 4 5 9 10

*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < r.size(); i++){
                     ~~^~~~~~~~~~
wiring.cpp:18:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < b.size(); i++){
                     ~~^~~~~~~~~~
wiring.cpp:23:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~

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