제출 #226901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226901		PedroBigMan	전선 연결 (IOI17_wiring)	C++14	0 / 100	1100 ms	23916 KiB

wiring

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include "wiring.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll)a; i<(ll)b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 100000000000000000LL
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
vector<ll> A,B; vector<ll> nearestA,nearestB;

ll f(ll s, ll t)
{
    if(s==0 && t==0) {return 0;}
    if(s==0)
    {
        ll ans=0LL; REP(i,0,t) {ans+=nearestB[i];}
        return ans;
    }
    if(t==0)
    {
        ll ans=0LL; REP(i,0,s) {ans+=nearestA[i];}
        return ans;
    }
    if(A[s-1]>B[t-1])
    {
        ll ans=f(s-1,t)+nearestA[s-1];
        REP(j,0,t)
        {
            ll val=f(s-1,j);
            REP(z,j,t) {val+=(A[s-1]-B[z]);}
            ans=min(ans,val);
        }
        return ans;
    }
    else if(A[s-1]<B[t-1])
    {
        ll ans=f(s,t-1)+nearestB[t-1];
        REP(j,0,s)
        {
            ll val=f(j,t-1);
            REP(z,j,s) {val+=(B[t-1]-A[z]);}
            ans=min(ans,val);
        }
        return ans;
    }
    return 0LL;
}

ll min_total_length(vector<int> xx, vector<int> yy) 
{
    REP(i,0,xx.size()) {A.pb((ll) xx[i]);}
    REP(i,0,yy.size()) {B.pb((ll) yy[i]);}
    vector<ll>::iterator it;
    REP(i,0,A.size()) {nearestA.pb(INF);}
    REP(i,0,B.size()) {nearestB.pb(INF);}
    REP(i,0,A.size())
    {
        it=lower_bound(whole(B),A[i]);
        if(it==B.end()) {nearestA[i]=A[i]-B[B.size()-1]; continue;}
        nearestA[i]=*it-A[i];
        if(it==B.begin()) {continue;}
        it--;
        nearestA[i]=min(nearestA[i],A[i]-*it);
    }
    REP(i,0,B.size())
    {
        it=lower_bound(whole(A),B[i]);
        if(it==A.end()) {nearestB[i]=B[i]-A[A.size()-1]; continue;}
        nearestB[i]=*it-B[i];
        if(it==A.begin()) {continue;}
        it--;
        nearestB[i]=min(nearestB[i],B[i]-*it);
    }
    return f(A.size(),B.size());
}

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