Submission #65998

#	Time	Username	Problem	Language	Result	Execution time	Memory
65998		FedericoS	Wiring (IOI17_wiring)	C++14	100 / 100	325 ms	90512 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],R[2][100005];
ll D,res,ans;

void insert(int k, int l, int r, int t, int g, int j, ll a){

    if(j<l or j>r)return;
    if(l==r)R[t][g][k]=a;
    else{

        int m=(l+r)/2;

        insert(2*k,l,m,t,g,j,a);
        insert(2*k+1,m+1,r,t,g,j,a);

        R[t][g][k]=min(R[t][g][2*k],R[t][g][2*k+1]);

    }

}

void inserisci(int g, int j, ll a){

    //cout<<"inserisci "<<g<<" "<<j<<" "<<a<<endl;

    insert(1,0,DP[g].size(),0,g,j,a);
    insert(1,0,DP[g].size(),1,g,j,a-((ll)DP[g].size()-j-1)*(V[g+1][0]-V[g][DP[g].size()-2]));
/*
    R[0][g][j]=a;
    R[1][g][j]=a-((ll)DP[g].size()-j-1)*(V[g+1][0]-V[g][DP[g].size()-2]);
*/
}

ll query(int k, int l, int r, int t, int g, int a, int b){

    if(b<l or r<a)return INF;
    if(a<=l and r<=b)return R[t][g][k];

    int m=(l+r)/2;

    return min(query(2*k,l,m,t,g,a,b),query(2*k+1,m+1,r,t,g,a,b));

}

ll minimo(int t, int g, int a, int b){
/*
    ll res2=INF;
    for(int i=a;i<b;i++)
        res2=min(res2,R[t][g][i]);
*/
    ll res=INF;

    if(b<=a)
        res=INF;
    else
        res=query(1,0,DP[g].size(),t,g,a,b-1);

    //cout<<"minimo "<<t<<" "<<g<<" "<<a<<" "<<b<<" "<<res<<" "<<res2<<endl;

    return res;

}

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

    for(int i=0;i<K;i++){
        R[0][i].resize(4*DP[i].size(),INF);
        R[1][i].resize(4*DP[i].size(),INF);
    }

    D=0;
    for(int i:V[0])
        D+=V[1][0]-i;
    DP[0][0]=D;
    inserisci(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(ll i=0;i<DP[g].size();i++){

            res=INF;
            res=min(res,minimo(0,g-1,0,(ll)DP[g-1].size()-i)+D);
            res=min(res,minimo(1,g-1,max((ll)DP[g-1].size()-i,0LL),(ll)DP[g-1].size())+D+(V[g][0]-V[g-1][DP[g-1].size()-2])*i);
/*
            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;
            inserisci(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:124:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i=0;i<DP[g].size();i++){
                    ~^~~~~~~~~~~~~
wiring.cpp:139:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i!=V[g].size()){
                ~^~~~~~~~~~~~~
wiring.cpp:157: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: 25 / 25
• Subtask 5: 45 / 45