Submission #673660

#	Time	Username	Problem	Language	Result	Execution time	Memory
673660		tbzard	Wiring (IOI17_wiring)	C++14	17 / 100	1098 ms	7740 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector<int> r, vector<int> b){
    vector<pair<int, int> > a;
    for(int i=0;i<r.size();i++) a.push_back(make_pair(r[i], 0));
    for(int i=0;i<b.size();i++) a.push_back(make_pair(b[i], 1));
    a.push_back(make_pair(-1, -1));
    sort(a.begin(), a.end());
    int n = r.size()+b.size();
    vector<int> sz(n+1);
    vector<long long> dp(n+1);
    for(int i=1;i<=n;i++) dp[i] = 1e18;

    for(int i=1;i<=n;i++){
        if(i == 1 || a[i].second != a[i-1].second) sz[i] = 1;
        else sz[i] = sz[i-1] + 1;

        long long sum0 = a[i].first, sum1 = 0;
        int color0 = 1, color1 = 0;

        if(i-sz[i] > 0) dp[i] = min(dp[i], dp[i-1] + a[i].first - a[i-sz[i]].first);
        for(int j=i-1;j>=1;j--){
            if(color1 && a[j].second == a[i].second) break;
            if(a[j].second == a[i].second){
                color0++;
                sum0 += a[j].first;
            }
            else{
                color1++;
                sum1 += a[j].first;
            }

            if(color0 > 0 && color1 > 0){
                if(color0 >= color1) dp[i] = min(dp[i], dp[j-1] + sum0 - sum1 - (color0-color1)*1ll*a[i-sz[i]].first);
                else dp[i] = min(dp[i], dp[j-1] + sum0 - sum1 + (color1-color0)*1ll*a[i-sz[i]+1].first);
            }
        }
    }
    return dp[n];
}

Compilation message (stderr)

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

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