Submission #1063875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063875		deera	Wiring (IOI17_wiring)	C++14	13 / 100	18 ms	5176 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
 
int d(int x, int y) {return abs(x - y);}
 
long long min_total_length(vector<int> r, vector<int> b) {
    int n = r.size(), m = b.size();
 
    if (r.back() < b.front()) {
        long long a = 0;
        for(int i: r) a += r.back() - i;
        for(int i: b) a += i - b.front();
        return a + (b.front() - r.back()) * max(r.size(), b.size());
    }
 
        int dp[201][201];
        dp[0][0] = d(r[0], b[0]);
        for(int i = 1; i < n; i++) dp[i][0] = dp[i-1][0] + d(r[i], b[0]);
        for(int i = 1; i < m; i++) dp[0][i] = dp[0][i-1] + d(r[0], b[i]);
        for(int i = 1; i < n; i++) 
            for(int j = max(i - 7, 1); j < min(i + 7, n); j++)
                dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + d(r[i], b[j]);
        return dp[n - 1][m - 1];
}

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