제출 #34675

#제출 시각아이디문제언어결과실행 시간메모리
34675mohammad_kilani전선 연결 (IOI17_wiring)C++14
30 / 100
1000 ms11836 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; #define red 1 #define blue 0 const int N = 200010; long long dp[N]; vector< pair<int,bool> > v; int n; long long solve(int i){ if(i == n) return 0; if(dp[i] != -1) return dp[i]; dp[i] = 1e18; int idx = -1; for(int j=i+1;j<n;j++){ if(v[j].second != v[i].second){ idx = j; break; } } if(idx == -1) return dp[i]; long long sum = 0; for(int j=i;j<idx;j++) sum += abs(v[idx].first - v[j].first); int idx2 = n; for(int j=idx+1;j<n;j++){ if(v[i].second == v[j].second){ idx2 = j; break; } } for(int j=idx;j<idx2;j++){ sum+= abs(v[j].first - v[idx].first); if(j - idx >= idx - i) sum += abs(v[idx].first - v[idx-1].first); dp[i] = min(dp[i],sum + solve(j+1)); } for(int j=idx2;j<n;j++){ if(v[j].second == v[idx].second) break; sum+= abs(v[j].first-v[idx].first); dp[i] = min(dp[i],sum + solve(j+1)); } return dp[i]; } long long min_total_length(std::vector<int> r, std::vector<int> b) { if(r.back() < b[0]){ int n =r.size() , m = b.size(); long long sum = 0 ; int idx = 0 ; int idx2 = 0; for(int i=0;i<min(n,m);i++) sum += abs(r[idx++] - b[idx2++]); for(int i=idx;i<r.size();i++) sum+= abs(r[i] - b[0]); for(int i=idx2;i<b.size();i++) sum+= abs(b[i] - r.back()); return sum; } memset(dp,-1,sizeof(dp)); int j =0 ; for(int i=0;i<r.size();i++){ while(j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++],blue)); v.push_back(make_pair(r[i],red)); } while(j < b.size()) v.push_back(make_pair(b[j++],blue)); n = v.size(); return solve(0); }

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

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=idx;i<r.size();i++) sum+= abs(r[i] - b[0]);
                  ^
wiring.cpp:55:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=idx2;i<b.size();i++) sum+= abs(b[i] - r.back());
                   ^
wiring.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<r.size();i++){
               ^
wiring.cpp:61:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++],blue));
           ^
wiring.cpp:64:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j < b.size()) v.push_back(make_pair(b[j++],blue));
          ^
#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...