제출 #1056869

#제출 시각아이디문제언어결과실행 시간메모리
1056869Baytoro전선 연결 (IOI17_wiring)C++17
0 / 100
1 ms348 KiB
#include "wiring.h" #include <bits/stdc++.h> #define ll long long #define pb push_back #define fr first #define sc second #define all(x) x.begin(),x.end() using namespace std; const ll INF=1e18; long long min_total_length(vector<int> r, vector<int> b) { int n = r.size(); int m = b.size(); vector<pair<int,int>> v; for(int i=0;i<n;i++){ v.pb({r[i],0}); } for(int i=0;i<m;i++){ v.pb({b[i],1}); } sort(all(v)); vector<vector<int>> t; int last=-1; for(int i=0;i<v.size();i++){ if(v[i].sc != last) t.pb({v[i].fr}); else t.back().pb(v[i].fr); } vector<ll> dp(t[0].size()+1,INF); dp[0]=0; for(int i=1;i<t.size();i++){ vector<ll> d(t[i].size()+1,INF); int r = dp.size(), l = t[i][0]-t[i-1].back(); vector<ll> f(r,INF); ll cnt = 0; for(int j=r-1;j>=0;j--){ f[j] = dp[j]+cnt; if(j>0) cnt+=(t[i-1].back()-t[i-1][j]); } vector<ll> pref(r+1,INF),suf(r+1,INF); for(int j=r-1;j>=0;j--){ suf[i] = min(suf[i+1],f[j]); } for(int j=0;j<r;j++){ if(j) pref[j]=pref[j-1]; pref[j] = min(pref[j],f[j]+(r-j-1)*l); } r--,cnt=0; for(int j=0;j<=t[i].size();j++){ d[j] = min(d[j],cnt+j*l+suf[max(0,r-j)]); if(r>=j) d[j] = min(d[j], cnt+pref[r-j]); if(j<t[i].size()) cnt+=(t[i][j]-t[i][0]); } swap(dp,d); } return dp.back(); }

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

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~
wiring.cpp:31:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i=1;i<t.size();i++){
      |              ~^~~~~~~~~
wiring.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int j=0;j<=t[i].size();j++){
      |               ~^~~~~~~~~~~~~
wiring.cpp:58:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    if(j<t[i].size())
      |       ~^~~~~~~~~~~~
#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...