Submission #240179

#	Time	Username	Problem	Language	Result	Execution time	Memory
240179		nicolaalexandra	Wiring (IOI17_wiring)	C++14	0 / 100	1090 ms	9208 KiB

wiring

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

long long dp[210][210],sp[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][j] = INF;
    }

    long long sum = 0;
    for (i=poz[1].first;i<=poz[1].second;i++)
        sum += a[i].first;
    dp[1][0] = -sum;

    /// 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_right = 0, sum_left = 0;
        for (j=Size[i];j>=0;j--){
            sum_left = sp[j];

            /// fixez cu care pot sa le cuplez din grupul anterior

            for (k=0;k<Size[i-1] && j;k++){
                if (dp[i-1][k] == INF) /// nu exista starea asta
                    continue;

                int nr1 = Size[i-1] - 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],dp[i-1][k] + sum_left + val);
            }

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

            sum_right -= a[poz[i].first+j-1].first;
        }


    }

    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: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45