제출 #240168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240168		nicolaalexandra	Wiring (IOI17_wiring)	C++14	7 / 100	43 ms	6264 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
#define DIM 210
#define INF 2000000000000000000LL
using namespace std;

long long dp[DIM][DIM];

int v[DIM],w[DIM];

int modul (int n){
    return max (n,-n);
}

int solve (int v[], int n, int val){
    int st = 1, dr = n, poz = 1;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (v[mid] <= val){
            poz = mid;
            st = mid+1;
        } else dr = mid-1;
    }

    int sol = modul(val - v[poz]);
    if (poz < n)
        sol = min (sol,modul(val - v[poz+1]));

    return sol;
}

long long min_total_length(vector<int> r, vector<int> b) {
    int n = 0, m = 0, i, j;
    for (auto it : r)
        v[++n] = it;
    for (auto it : b)
        w[++m] = it;

    sort (v+1,v+n+1);
    sort (w+1,w+m+1);

    /// dp[i][j] - costul minim sa conectez primele i puncte rosii cu primele j puncte albastre
    for (i=1;i<=m;i++)
        dp[1][i] = dp[1][i-1] + modul (v[1] - w[i]);
    for (i=1;i<=n;i++)
        dp[i][1] = dp[i-1][1] + modul (v[i] - w[1]);

    for (i=2;i<=n;i++)
        for (j=2;j<=m;j++){
            dp[i][j] = INF;
            dp[i][j] = min (dp[i][j], dp[i-1][j-1] + modul(v[i]-w[j]));
            dp[i][j] = min (dp[i][j], dp[i][j-1] + solve (v,n,w[j]));
            dp[i][j] = min (dp[i][j],dp[i-1][j] + solve (w,m,v[i]));
        }

    return dp[n][m];
}

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