Submission #598021

#	Time	Username	Problem	Language	Result	Execution time	Memory
598021		Lucpp	Wiring (IOI17_wiring)	C++17	7 / 100	1087 ms	5324 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll min_total_length(vector<int> r, vector<int> b) {
	int n = int(r.size()), m = int(b.size());
	vector<ll> dp(m+1, INF);
    dp[0] = 0;
    for(int i = 0; i < n; i++){
        vector<ll> dp2(m+1, INF);
        for(int j = 1; j <= m; j++){
            dp2[j] = min(dp2[j], dp[j]+abs(b[j-1]-r[i]));
            ll cost = 0;
            for(int k = j-1; k >= 0; k--){
                cost += abs(b[k]-r[i]);
                dp2[j] = min(dp2[j], dp[k]+cost);
            }
            // cerr << i << " " << j << " " << dp2[j] << "\n";
        }
        dp = dp2;
    }
    return dp[m];
}

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