제출 #609023

#제출 시각아이디문제언어결과실행 시간메모리
609023PiejanVDC전선 연결 (IOI17_wiring)C++17
0 / 100
34 ms8380 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; long long min_total_length(vector<int>r, vector<int>b) { const int n = (int)r.size(), m = (int)b.size(); long long dp[45][45]; for(int i = 0 ; i <= 39 ; i++) for(int j = 0 ; j <= 39 ; j++) dp[i][j] = 1e15; dp[0][0] = 0; int a = 0, c = 0; vector<pair<int,int>>v; bool ok = 1; int f, cnt = 0; for(int i = 0 ; i < n+m ; i++) { if(a == n) {v.push_back({1, b[c++]}); continue;} if(c == m) {v.push_back({0, r[a++]}); continue;} if(r[a] < b[c]) v.push_back({0, r[a++]}); else v.push_back({1, b[c++]}); if(i == 0) f = v.back().first; if(ok && v.back().first == f) cnt++; else ok = 0; } int del = 0; int A = 0, B = 0; if(f) B = cnt; else A = cnt; while(A+B < n+m) { int len = 0; c = v[A+B].first; int ii = A+B; while(ii < n+m && v[ii].first == c) ii++, len++; ii = A+B-1; c = 1 - c; int prev = 0; while(ii >= 0 && v[ii].first == c) ii--, prev++; c = 1 - c; int mn = INT_MAX; cnt = 0; for(int ii = A+B ; ii < A+B+len ; ii++) { cnt++; if(c == 0) { int i = A+(ii - (A+B)+1); for(int j = B-prev+1 ; j <= B ; j++) { for(int k = B-prev+1 ; k <= B ; k++) dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-del] + abs(v[ii].second - v[k+A-1].second)); for(int k = A+(ii - (A+B)+1) ; k <= A+len ; k++) dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-del][j-1-del] + abs(v[j+A-1].second - v[k+B-1].second)); dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-1-del] + abs(v[ii].second - v[j+A-1].second)); mn = min(i-1-del, j-1-del); assert(mn >= 0); } } else { int j = B + (ii - (A+B)+1); for(int i = A-prev+1 ; i <= A ; i++) { for(int k = A-prev+1 ; k <= A ; k++) dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-del][j-1-del] + abs(v[ii].second - v[k+B-1].second)); for(int k = B+(ii - (A+B)+1) ; k <= B+len ; k++) dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-del] + abs(v[i+B-1].second - v[k+A-1].second)); dp[i-del][j-del] = min(dp[i-del][j-del], dp[i-1-del][j-1-del] + abs(v[ii].second - v[i+B-1].second)); mn = min(j-1-del, i-1-del); assert(mn >= 0); } } } if(c) B += len; else A += len; int d = 0; if(cnt == 4) { cnt = 0; d += mn; } del += d; for(int i = 0 ; i <= 39 ; i++) for(int j = 0 ; j <= 39 ; j++) dp[i][j] = (i+d <= 39 && j+d <= 39 ? dp[i+d][j+d] : 1e15); } return dp[n-del][m-del]; }

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

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:34:5: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |     if(f) B = cnt;
      |     ^~
#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...