Submission #377685

#	Time	Username	Problem	Language	Result	Execution time	Memory
377685		Sorting	Wiring (IOI17_wiring)	C++17	7 / 100	33 ms	5612 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

template<typename T> void check_min(T &a, const T b){a = (a < b) ? a : b;}
const int N = 200 + 3;
const ll INF = 1e18;

ll dp[N][N];

ll min_total_length(vector<int> r, vector<int> b) {
	dp[r.size()][b.size()] = 0;
    for(int j = (int)b.size() - 1; j >= 0; --j)
        dp[r.size()][j] = INF;

    for(int i = (int)r.size() - 1; i >= 0; --i){
        dp[i][b.size()] = INF;
        for(int j = (int)b.size() - 1; j >= 0; --j){
            dp[i][j] = INF;
            check_min(dp[i][j], dp[i + 1][j + 1] + abs(r[i] - b[j]));
            check_min(dp[i][j], dp[i + 1][j] + abs(r[i] - b[j]));
            check_min(dp[i][j], dp[i][j + 1] + abs(r[i] - b[j]));
        }
    }
    return dp[0][0];
}

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