제출 #65994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65994		FedericoS	전선 연결 (IOI17_wiring)	C++14	30 / 100	1070 ms	39320 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 inserisci(int g, int j, int a){

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

    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 t, int x, int a, int b){

    ll res=INF;
    for(int i=a;i<b;i++)
        res=min(res,R[t][x][i]);
    //cout<<"query "<<t<<" "<<x<<" "<<a<<" "<<b<<" "<<res<<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,query(0,g-1,0,(ll)DP[g-1].size()-i)+D);
            res=min(res,query(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;
    }
*/

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:84:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i=0;i<DP[g].size();i++){
                    ~^~~~~~~~~~~~~
wiring.cpp:99:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i!=V[g].size()){
                ~^~~~~~~~~~~~~
wiring.cpp:117: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