제출 #132575

#제출 시각아이디문제언어결과실행 시간메모리
132575rondojim전선 연결 (IOI17_wiring)C++17
55 / 100
1032 ms15828 KiB
#include "wiring.h" #include<bits/stdc++.h> typedef long long ll; #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; ll n,i,te,d[202020]; pair<ll,ll> a[202020]; ll com(ll aa,ll bb) { ll ii; vector<ll> x,y; for(ii=aa;ii<=bb;ii++) if(a[ii].se==a[aa].se) x.pb(a[ii].fi); else y.pb(a[ii].fi); ll H=0; reverse(x.begin(),x.end()); if(x.size()<y.size()) { for(ii=0;ii<x.size();ii++) H+=abs(x[ii]-y[ii]); for(ii=x.size();ii<y.size();ii++) H+=abs(x[0]-y[ii]); } else { for(ii=0;ii<y.size();ii++) H+=abs(x[ii]-y[ii]); for(ii=y.size();ii<x.size();ii++) H+=abs(y[0]-x[ii]); } //cout<<aa<<" "<<bb<<" "<<H<<"\n"; return H; } ll depe(ll aa) { if(aa==n+1) return 0; if(d[aa]==-1) { d[aa]=1e18; ll ii,udh=0; vector<ll> z; for(ii=aa;ii<=n;ii++) { if(ii>aa&&a[ii].se!=a[ii-1].se) udh=1; if(udh&&a[ii].se==a[aa].se) break; if(udh) { z.pb(ii); if(n!=a[n].fi) d[aa]=min(d[aa],com(aa,ii)+min(depe(ii+1),depe(ii))); } } ll zs=z.size(); if(zs==1) { for(ii=0;ii<zs;ii++) d[aa]=min(d[aa],com(aa,z[ii])+min(depe(z[ii]+1),depe(z[ii]))); } else if(zs) { // cout<<zs<<" "<<zs/2-1<<" "<<zs/2-1+(zs%2==1)<<"\n"; for(ii=zs/2-1;ii<=zs/2-1+(zs%2==1);ii++) d[aa]=min(d[aa],com(aa,z[ii])+min(depe(z[ii]+1),depe(z[ii]))); } if(zs) for(ii=zs-1;ii<=zs-1;ii++) d[aa]=min(d[aa],com(aa,z[ii])+min(depe(z[ii]+1),depe(z[ii]))); } return d[aa]; } long long min_total_length(std::vector<int> r, std::vector<int> b) { n=r.size()+b.size(); for(i=0;i<r.size();i++) a[++te]=mp(r[i],0); for(i=0;i<b.size();i++) a[++te]=mp(b[i],1); if(r[r.size()-1]<b[0]) return com(1,n); sort(a+1,a+1+te); memset(d,-1,sizeof(d)); return depe(1); }

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

wiring.cpp: In function 'll com(ll, ll)':
wiring.cpp:24:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<x.size();ii++)
            ~~^~~~~~~~~
wiring.cpp:26:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=x.size();ii<y.size();ii++)
                   ~~^~~~~~~~~
wiring.cpp:31:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<y.size();ii++)
            ~~^~~~~~~~~
wiring.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=y.size();ii<x.size();ii++)
                   ~~^~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:82:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<r.size();i++)
          ~^~~~~~~~~
wiring.cpp:84:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<b.size();i++)
          ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...