제출 #226944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226944		PedroBigMan	Wiring (IOI17_wiring)	C++14	20 / 100	208 ms	262148 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; vector<vector<ll> > dp;
 
ll f(ll s, ll t)
{
    if(dp[s][t]!=INF) {return dp[s][t];}
    if(s==0 && t==0) {dp[0][0]=0;return 0;}
    if(s==0)
    {
        ll ans=0LL; REP(i,0,t) {ans+=nearestB[i];}
        dp[s][t]=ans;
        return ans;
    }
    if(t==0)
    {
        ll ans=0LL; REP(i,0,s) {ans+=nearestA[i];}
        dp[s][t]=ans;
        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);
        }
        dp[s][t]=ans;
        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);
        }
        dp[s][t]=ans;
        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]);}
    if(A[A.size()-1]<B[0])
    {
        ll ans=0LL;
        REP(i,0,B.size()) {ans+=(ll) B[i];}
        REP(i,0,A.size()) {ans-=(ll) A[i];}
        if(A.size()<=B.size()) 
        {
            REP(i,0,B.size()-A.size()) {ans-=A[A.size()-1];}
        }
        else 
        {
            REP(i,0,A.size()-B.size()) {ans+=B[0];}
        }
        return ans;
    }
    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);
    }
    vector<ll> xxx; REP(i,0,B.size()+1) {xxx.pb(INF);}
    REP(i,0,A.size()+1) {dp.pb(xxx);}
    return f(A.size(),B.size());
}

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

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:18:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=(ll)a; i<(ll)b; i++)
wiring.cpp:86:17:
             REP(i,0,B.size()-A.size()) {ans-=A[A.size()-1];}
                 ~~~~~~~~~~~~~~~~~~~~~
wiring.cpp:86:13: note: in expansion of macro 'REP'
             REP(i,0,B.size()-A.size()) {ans-=A[A.size()-1];}
             ^~~
wiring.cpp:18:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=(ll)a; i<(ll)b; i++)
wiring.cpp:90:17:
             REP(i,0,A.size()-B.size()) {ans+=B[0];}
                 ~~~~~~~~~~~~~~~~~~~~~
wiring.cpp:90:13: note: in expansion of macro 'REP'
             REP(i,0,A.size()-B.size()) {ans+=B[0];}
             ^~~

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