Submission #240202

#	Time	Username	Problem	Language	Result	Execution time	Memory
240202		nicolaalexandra	Wiring (IOI17_wiring)	C++14	17 / 100	1093 ms	14200 KiB

wiring

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

long long sp[DIM];
vector <long long> dp[DIM];
int Size[DIM];
pair <int,int> a[DIM],poz[DIM];


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


long long min_total_length(vector<int> r, vector<int> b) {
    int i, j, n = 0;

    /// impart in grupuri cu elemente de aceasi tip
    /// dp[i][j] - costul minim daca ajung la grupul i si primele j elemente din grupul asta\
    sunt conectate la grupul anterior

    int k = 0;
    for (auto it : r)
        a[++k] = make_pair(it,0);
    for (auto it : b)
        a[++k] = make_pair(it,1);
    sort (a+1,a+k+1);

    i = 1;
    while (i <= k){

        int j = i, nr = 0;
        while (j <= k && a[j].second == a[i].second){
            nr++;
            j++;
        }

        Size[++n] = nr;
        poz[n] = make_pair(i,i+nr-1);

        i = j;
    }

    for (i=1;i<=n;i++){
        for (j=0;j<=Size[i];j++)
            dp[i].push_back(INF);
    }

    dp[1][0] = 0;

    /// nu stiu cat de bine o sa mearga asta dar n am alta solutie mai buna

    for (i=2;i<=n;i++){

        int pas = 1;
        for (j=poz[i].first;j<=poz[i].second;j++){
            sp[pas] = sp[pas-1] + a[j].first;
            pas++;
        }

        long long sum_left = 0;
        for (j=Size[i];j>=0;j--){
            sum_left = sp[j];

            /// fixez cu care pot sa le cuplez din grupul anterior
            long long sum_right = 0, mini = dp[i-1][Size[i-1]];
            for (k=1;k<=Size[i-1] && j;k++){

                mini = min (mini,dp[i-1][Size[i-1]-k]);

                sum_right -= a[ poz[i-1].second - k + 1 ].first;

                int nr1 = k, nr2 = j; long long val = 0;
                if (nr1 < nr2)
                    val -= 1LL * (nr2 - nr1) * a[ poz[i-1].second ].first;
                else val += 1LL * (nr1 - nr2) * a[ poz[i].first ].first;

                dp[i][j] = min (dp[i][j],mini + sum_left + sum_right + val);
            }

            if (!j && dp[i-1][Size[i-1]] != INF)
                dp[i][j] = dp[i-1][Size[i-1]];
        }
    }

    return dp[n][Size[n]];

}

Compilation message (stderr)

wiring.cpp:22:5: warning: multi-line comment [-Wcomment]
     /// dp[i][j] - costul minim daca ajung la grupul i si primele j elemente din grupul asta\
     ^

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