Submission #240170

#	Time	Username	Problem	Language	Result	Execution time	Memory
240170		nicolaalexandra	Wiring (IOI17_wiring)	C++14	20 / 100	47 ms	4600 KiB

wiring

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

long long dp[210][210];

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);

    if (n <= 200 && m <= 200){
        /// 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];
    }

    if (v[n] < w[1]){
        long long sol = 0;
        for (i=1;i<=n;i++)
            sol -= v[i];
        for (i=1;i<=m;i++)
            sol += w[i];
        if (n < m)
            sol -= 1LL * v[n] * (m-n);
        else sol += 1LL * w[1] * (n-m);

        return sol;
    }

}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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