Submission #1072549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072549		ArthuroWich	Wiring (IOI17_wiring)	C++17	0 / 100	0 ms	348 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int pref[200005];
void init(int n, vector<pair<int, int>> &a) {
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i-1]+a[i-1].first;
    }
}
int query(int l, int r) {
    int x = min(l, r);
    r = max(l, r);
    l = x;
    l++;
    r++;
    return pref[r]-pref[l-1];
}
int calc(vector<int> &r, vector<int> &b) {
    int ans = 0, rbe, bbe;
    rbe = r.front();
    bbe = b.front();
    ans += query(b[0], b[min(r.size(), b.size())-1])-query(r[0], r[min(r.size(), b.size())-1]);
    if (r.size() < b.size()) {
        int x = b.size()-r.size();
        ans += query(b[r.size()], b[b.size()-1])-rbe*x;
    } else if (r.size() > b.size()) {
        int x = (int)r.size()-b.size();
        ans += bbe*x-query(r[b.size()], r[r.size()-1]);
    }
    return ans;
}
int min_total_length(vector<int32_t> r, vector<int32_t> b) {
    int n = r.size()+b.size();
    vector<pair<int, int>> a;
    for (int i = 0; i < r.size(); i++) {
        a.push_back({r[i], 0});
    }
    for (int i = 0; i < b.size(); i++) {
        a.push_back({b[i], 1});
    }
    vector<int> dp(n, INT64_MAX);
    sort(a.begin(), a.end());
    init(n, a);
    for (int i = 1; i < n; i++) {
        int l = -1, r = i;
        vector<int> lv, rv;
        for (int j = i; j >= 0; j--) {
            if (a[j].second != a[r].second) {
                l = j;
                break;
            } else {
                rv.push_back(j);
            }
        }
        if (l == -1) {
            continue;
        }
        reverse(rv.begin(), rv.end());
        if (dp[i-1] != INT64_MAX) {
            dp[i] = min(dp[i], dp[i-1]+abs(a[r].first-a[l].first));
        }
        for (int j = l; j >= 0; j--) {
            if (a[j].second == a[l].second) {
                lv.push_back(j);
                if (j-1 >= 0) {
                    if (dp[j-1] == INT64_MAX) {
                        continue;
                    }
                    dp[i] = min(dp[i], dp[j-1]+calc(lv, rv));
                } else if (j == 0) {
                    dp[i] = min(dp[i], calc(lv, rv));
                }
            } else {
                break;
            }
        }
    }
    return dp[n-1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:36:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
wiring.cpp:39:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     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