Submission #65987

#	Time	Username	Problem	Language	Result	Execution time	Memory
65987		FedericoS	Wiring (IOI17_wiring)	C++14	30 / 100	1075 ms	45952 KiB

wiring

#include <iostream>
#include <algorithm>
#include "wiring.h"
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

ll INF=1e18;
int N,M,K;
ll A[100005],B[100005];
vector<pll> W;
vector<ll> DP[100005],V[100005];
ll D,res,ans;

void stampa(){
    for(int i=0;i<K;i++){
        cout<<"gruppo "<<i<<endl;
        for(ll g:DP[i])
            cout<<g<<" ";
        cout<<endl;
    }
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {

    N=r.size();
    M=b.size();

    for(int a:r)
        W.push_back({a,0});
    for(int a:b)
        W.push_back({a,1});
    sort(W.begin(),W.end());

    V[0].push_back(W[0].first);
    DP[0].push_back(INF);
    for(int i=1;i<N+M;i++){
        if(W[i].second!=W[i-1].second)
            K++;
        V[K].push_back(W[i].first);
        DP[K].push_back(INF);
    }
    K++;

    for(int i=0;i<K;i++)
        DP[i].push_back(INF);

    D=0;
    for(int i:V[0])
        D+=V[1][0]-i;
    DP[0][0]=D;

    for(int g=1;g<K-1;g++){

        D=0;
        for(int i:V[g])
            D+=V[g+1][0]-i;

        for(int i=0;i<DP[g].size();i++){

            res=INF;

            for(int j=0;j<(int)DP[g-1].size()-i;j++)
                res=min(res,DP[g-1][j]+D);

            for(int j=max((int)DP[g-1].size()-i,0);j<DP[g-1].size();j++)
                res=min(res,DP[g-1][j]+D+(i-(ll)DP[g-1].size()+j+1)*(V[g][0]-V[g-1][DP[g-1].size()-2]));

            DP[g][i]=res;

            if(i!=V[g].size()){
                D-=V[g+1][0]-V[g][i];
                D+=V[g][i]-V[g][0];
            }
        }
    }

    D=0;
    for(int i:V[K-1])
        D+=i-V[K-1][0];

    ans=INF;
    int g=K-1;
    int i=(int)DP[g].size()-1;

    for(int j=0;j<(int)DP[g-1].size()-i;j++)
        ans=min(ans,DP[g-1][j]+D);

    for(int j=max((int)DP[g-1].size()-i,0);j<DP[g-1].size();j++)
        ans=min(ans,DP[g-1][j]+D+(i-(ll)DP[g-1].size()+j+1)*(V[g][0]-V[g-1][DP[g-1].size()-2]));

    //stampa();

    return ans;

}

/*
4 5
1 2 3 7
0 4 5 9 10
*/
/*
    for(int i=0;i<K;i++){
        cout<<"i "<<i<<endl;
        for(int g:V[i])
            cout<<g<<" ";
        cout<<endl;
    }
*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<DP[g].size();i++){
                     ~^~~~~~~~~~~~~
wiring.cpp:66:53: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=max((int)DP[g-1].size()-i,0);j<DP[g-1].size();j++)
                                                    ~^~~~~~~~~~~~~~~
wiring.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i!=V[g].size()){
                ~^~~~~~~~~~~~~
wiring.cpp:89:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=max((int)DP[g-1].size()-i,0);j<DP[g-1].size();j++)
                                            ~^~~~~~~~~~~~~~~

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