Submission #673622

#	Time	Username	Problem	Language	Result	Execution time	Memory
673622		tbzard	Wiring (IOI17_wiring)	C++14	0 / 100	1 ms	212 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));
    int n = r.size()+b.size();
    sort(a.begin(), a.end());
    vector<int> sz(n+1);
    vector<long long> dp(n+1);
    int R = -1, B = -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 if(a[i].second == a[i-1].second) sz[i] = sz[i-1] + 1;

        if(a[i].second == 0) R = i;
        else B = -1;

        long long sum0 = 0, sum1 = 0;
        int color0 = 0, color1 = 0;
        for(int j=i;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 >= 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));
      |                 ~^~~~~~~~~
wiring.cpp:12:9: warning: variable 'R' set but not used [-Wunused-but-set-variable]
   12 |     int R = -1, B = -1;
      |         ^
wiring.cpp:12:17: warning: variable 'B' set but not used [-Wunused-but-set-variable]
   12 |     int R = -1, B = -1;
      |                 ^

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