Submission #406809

#	Time	Username	Problem	Language	Result	Execution time	Memory
406809		wiwiho	Wiring (IOI17_wiring)	C++14	17 / 100	1085 ms	11284 KiB

wiring

#include "wiring.h"

#include<bits/stdc++.h>

#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define eb emplace_back

using namespace std;

typedef long long ll;

using pii = pair<int, int>;

const ll MAX = 1LL << 60;

ostream& operator<<(ostream& o, pii p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll min_total_length(vector<int> r, vector<int> b) {
    int n = r.size(), m = b.size();

    vector<pii> a;
    for(int i : r) a.eb(mp(i, 0));
    for(int i : b) a.eb(mp(i, 1));
    lsort(a);

    vector<vector<int>> pos;
    int lst = -1;
    for(pii i : a){
        if(i.S != lst) pos.eb();
        pos.back().eb(i.F);
        lst = i.S;
    }
    //for(auto i : pos) printv(i, cerr);

    vector<vector<ll>> dp(pos.size());
    dp[0].resize(pos[0].size() + 1, MAX);
    dp[0][pos[0].size()] = 0;
    for(int i = 0; i < pos[0].size(); i++){
        dp[0][pos[0].size()] += pos[0].back() - pos[0][i];
    }

    //cerr << "test 0\n";
    //printv(dp[0], cerr);
    for(int i = 1; i < pos.size(); i++){
        int cnt = pos[i].size();
        dp[i].resize(cnt + 1, MAX);
        for(int j = 0; j <= cnt; j++){
            ll tmp = 0;
            for(int k = 0; k < j; k++) tmp += pos[i][k] - pos[i][0];
            for(int k = j; k < cnt; k++) tmp += pos[i][cnt - 1] - pos[i][k];
            //cerr << "OAO " << i << " " << j << " " << tmp << "\n";
            for(int k = 0; k < dp[i - 1].size(); k++){
                dp[i][cnt - j] = min(dp[i][cnt - j], dp[i - 1][k] + tmp + (ll)max(k, j) * (pos[i].front() - pos[i - 1].back()));
            }
        }
        //cerr << "test " << i << "\n";
        //printv(dp[i], cerr);
    }

    return dp.back()[0];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0; i < pos[0].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
wiring.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 1; i < pos.size(); i++){
      |                    ~~^~~~~~~~~~~~
wiring.cpp:62:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(int k = 0; k < dp[i - 1].size(); k++){
      |                            ~~^~~~~~~~~~~~~~~~~~
wiring.cpp:29:9: warning: unused variable 'n' [-Wunused-variable]
   29 |     int n = r.size(), m = b.size();
      |         ^
wiring.cpp:29:23: warning: unused variable 'm' [-Wunused-variable]
   29 |     int n = r.size(), m = b.size();
      |                       ^

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