제출 #142837

#제출 시각아이디문제언어결과실행 시간메모리
142837babo전선 연결 (IOI17_wiring)C++14
13 / 100
79 ms19448 KiB
#include <bits/stdc++.h> #define inf 2000000000 #define all(x) (x).begin(),(x).end() #define L long long using namespace std; struct S{ L loc,det,chk,lev,milen; }a[200020]; L dp[200020]; vector<L>v[200020]; L n,m; L min_total_length(vector<int>r, vector<int>b){ sort(all(r)); sort(all(b)); n=r.size(); m=b.size(); L i,ret=0; for(i=0;i<n;i++) { a[i]=(S){r[i],1,0}; } for(i=n;i<n+m;i++) { a[i]=(S){b[i-n],2,0}; } sort(a,a+n+m,[](S a,S b){ return a.loc<b.loc; }); L lev=100010; for(i=0;i<n+m;i++) { a[i].lev=lev; v[lev].push_back(i); if(a[i].det==1&&a[i+1].det==1) lev++; if(a[i].det==2&&a[i+1].det==2) lev--; //printf("%lld %lld\n",a[i].det,a[i].loc); } for(i=0;i<n+m;i++) { L mi=inf; vector<int>::iterator it; if(a[i].det==1) { it=lower_bound(all(b),a[i].loc); if(it!=b.end()) mi=min(mi,*it-a[i].loc); it=upper_bound(all(b),a[i].loc); if(it!=b.begin()) mi=min(mi,a[i].loc-*(prev(it))); } else { it=lower_bound(all(r),a[i].loc); if(it!=r.end()) mi=min(mi,*it-a[i].loc); it=upper_bound(all(r),a[i].loc); if(it!=r.begin()) mi=min(mi,a[i].loc-*(prev(it))); } a[i].milen=mi; //printf("%lld ",a[i].milen); } //puts(""); for(lev=0;lev<200020;lev++) { if(v[lev].size()%2==0) { for(i=0;i<v[lev].size();i+=2) { ret+=a[v[lev][i+1]].loc-a[v[lev][i]].loc; } } else { for(i=0;i<=v[lev].size();i++) dp[i]=inf; dp[0]=0; for(i=0;i<=v[lev].size();i++) { if(i>=2) dp[i]=min(dp[i],dp[i-2]+a[v[lev][i-1]].loc-a[v[lev][i-2]].loc); if(i>=1) dp[i]=min(dp[i],dp[i-1]+a[v[lev][i-1]].milen); if(i>=2) dp[i]=min(dp[i],dp[i-2]+a[v[lev][i-1]].loc-a[v[lev][i-2]].loc); } //for(i=0;i<=v[lev].size();i++) // printf("%lld %lld\n",dp[i][0],dp[i][1]); ret+=dp[v[lev].size()]; } } return ret; }

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

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:74:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v[lev].size();i+=2)
            ~^~~~~~~~~~~~~~
wiring.cpp:81:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<=v[lev].size();i++)
            ~^~~~~~~~~~~~~~~
wiring.cpp:84:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<=v[lev].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...