Submission #584038

#	Time	Username	Problem	Language	Result	Execution time	Memory
584038		yanndev	Wiring (IOI17_wiring)	C++17	20 / 100	29 ms	4652 KiB

wiring

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
// st2 13pts at 47mn
// st1 7pts at 1h04
const ll OO = 1e16;
 
int n, m;
ll dp[201][201];
vector<int> R {};
vector<int> B {};
 
ll solve(int rPos, int bPos) {
    if (rPos == n && bPos == m)
        return 0;
    if (rPos == n || bPos == m)
        return OO;
    if (dp[rPos][bPos] != -1)
        return dp[rPos][bPos];
    
    // link rPos and bPos and then extend to one of them
    ll dif = abs(R[rPos] - B[bPos]);
    return dp[rPos][bPos] = dif + min({solve(rPos + 1, bPos), solve(rPos, bPos + 1), solve(rPos + 1, bPos + 1)});
}
 
ll min_total_length(vector<int> r, vector<int> b) {
    R = r;
    B = b;
    n = (int)r.size();
    m = (int)b.size();
    
    if (n <= 200 && m <= 200) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                dp[i][j] = -1;
        return solve(0, 0);
    }
 
    ll ans = 0;
 
    if ((int)r.size() > (int)b.size()) {
        for (int i = 0; i < (int)b.size(); i++) {
            //cout << "blue " << i << " red " << (int)r.size() - i - 1 << '\n';
            ans += b[i] - r[(int)r.size() - i - 1];
        }
        for (int j = (int)r.size() - (int)b.size() - 1; j >= 0; j--) {
            //cout << "blue " << 0 << " red " << j << '\n';
            ans += b[0] - r[j];
        }
    } else {
        for (int i = 0; i < (int)r.size(); i++)
            ans += b[(int)r.size() - i - 1] - r[i];
        for (int j = (int)r.size(); j < (int)b.size(); j++)
            ans += b[j] - r.back();
    }
 
    return ans;
}

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