Submission #406703

#	Time	Username	Problem	Language	Result	Execution time	Memory
406703		wiwiho	Wiring (IOI17_wiring)	C++14	7 / 100	541 ms	3520 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();

    assert(n <= 200);

    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<ll>> dp(n + m + 1, vector<ll>(n + m + 1, MAX));
    dp[0][0] = 0;

    ll lst = a[0].F;
    for(pii now : a){
        vector<vector<ll>> dp2(n + m + 1, vector<ll>(n + m + 1, MAX));
        for(int i = 0; i <= n + m; i++){
            for(int j = 0; j <= n + m; j++){
                if(dp[i][j] == MAX) continue;
                dp[i][j] += (ll)(i + j) * (now.F - lst);
            }
        }
        if(now.S == 0){
            for(int i = 0; i <= n + m; i++){
                for(int j = n + m; j > 0; j--){
                    dp2[i][j - 1] = min({dp2[i][j - 1], dp[i][j], dp2[i][j]});
                }
            }
            for(int i = 0; i < n + m; i++){
                for(int j = 0; j <= n + m; j++){
                    dp2[i + 1][j] = min({dp2[i + 1][j], dp[i][j], dp2[i][j]});
                }
            }
        }
        else{
            for(int i = n + m; i > 0; i--){
                for(int j = 0; j <= n + m; j++){
                    dp2[i - 1][j] = min({dp2[i - 1][j], dp[i][j], dp2[i][j]});
                }
            }
            for(int i = 0; i <= n + m; i++){
                for(int j = 0; j < n + m; j++){
                    dp2[i][j + 1] = min({dp2[i][j + 1], dp[i][j], dp2[i][j]});
                }
            }
        }
        dp = dp2;
        lst = now.F;
        //cerr << "test " << now.F << " " << now.S << "\n";
        //for(int i = 0; i <= n; i++) printv(dp[i], cerr);
    }

	return dp[0][0];
}

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