Submission #574611

#	Time	Username	Problem	Language	Result	Execution time	Memory
574611		definitelynotmee	Wiring (IOI17_wiring)	C++98	20 / 100	22 ms	3760 KiB

wiring

#include<bits/stdc++.h>
#include"wiring.h"
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const ll INFL = (1ll<<60)-1;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
    int n = r.size(), m = b.size();
    ll resp = 0;
    if(r.back() < b[0]){
            
        for(int i = 0; i < n; i++)
            resp-=r[i];
        for(int i = 0; i < m; i++)
            resp+=b[i];
        while(n > m){
            resp+=b[0];
            n--;
        }
        while(m > n){
            resp-=r.back();
            m--;
        }
    } else if(n <= 200 && m <= 200) {
        matrix<ll> dp(n,vector<ll>(m,-1));
        auto calc =[&](int red, int blue, auto calc)->ll{
            if(red == n && blue == m)
                return 0;
            if(red == n || blue == m)
                return INFL;

            if(dp[red][blue] != -1){
                return dp[red][blue];
            }
            dp[red][blue] = INFL;
            ll cur = 0;
            cur+=abs(b[blue]-r[red]);
            dp[red][blue] = min({cur+calc(red+1,blue,calc), cur+calc(red+1,blue+1,calc),cur+calc(red,blue+1,calc)});
            return dp[red][blue];
        };
        resp = calc(0,0,calc);
    }
    
    
	return resp;
}
//3 + 6 + 9 + 7 = 9 + 16 = 25

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