Submission #968754

#	Time	Username	Problem	Language	Result	Execution time	Memory
968754		12345678	Wiring (IOI17_wiring)	C++17	7 / 100	1073 ms	4784 KiB

wiring

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

#define ll long long

using namespace std;

const int nx=205;

ll dp[nx][nx];
vector<int> R, B;

ll greedyr(ll x)
{
    ll res=LLONG_MAX;
    for (auto y:B) res=min(res, abs(x-y));
    return res;
}

ll greedyb(ll x)
{
    ll res=LLONG_MAX;
    for (auto y:R) res=min(res, abs(x-y));
    return res;
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
    R=r, B=b;
	int n=r.size(), m=b.size();
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            dp[i][j]=LLONG_MAX;
            if (i>0) dp[i][j]=min(dp[i][j], dp[i-1][j]+greedyr(r[i]));
            if (j>0) dp[i][j]=min(dp[i][j], dp[i][j-1]+greedyb(b[j]));
            if (i==0&&j==0) dp[i][j]=abs(r[i]-b[j]);
            if (i>0&&j>0) dp[i][j]=min(dp[i][j], dp[i-1][j-1]+abs(r[i]-b[j]));
        }
    }
    return dp[n-1][m-1];
}

/*
4 5
1 3 4 5
8 9 10 12 14
*/

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