제출 #125318

#제출 시각아이디문제언어결과실행 시간메모리
125318turbat전선 연결 (IOI17_wiring)C++14
0 / 100
45 ms5736 KiB
#include <bits/stdc++.h> #include "wiring.h" using namespace std; long long dp[200005], sum[200005]; pair <int , int> p[100005]; int n, m; long long cost(int l, int r, int to){ if (r - l + 1 < to - r) return sum[to] - 2 * sum[r] + sum[l - 1] - 1ll * (to - r - r + l - 1) * p[r].first; return sum[to] - 2 * sum[r] + sum[l - 1] + 1ll * (r - l + 1 - to + r) * p[r + 1].first; } void solve (int l, int r){ if (r == n + m) return; // cout << l << ' ' << r<< endl; int curr = r + 1; while (curr <= n + m){ dp[curr] = 2e18; for (int curl = l;curl <= r;curl++) dp[curr] = min (dp[curr], dp[curl - 1] + cost(curl, r, curr)); if (p[curr].second != p[curr + 1].second){ solve(r + 1, curr); break; } curr++; } } long long min_total_length(vector<int> r, vector<int> b) { int l = 0, l1 = 0; n = r.size(), m = b.size(); p[n + m + 1].second = 2; r.push_back(2e9); b.push_back(2e9); for (int i = 1;i <= n + m;i++){ sum[i] = sum[i - 1]; sum[i] += min(r[l], b[l1]); p[i].first = min(r[l], b[l1]); if (r[l] > b[l1]){ p[i].second = 1; l1++; } else l++; } int bg; for (int i = 2;i <= n + m;i++) if (p[i].second != p[i - 1].second){ bg = i - 1; break; } for (int i = bg + 1;i <= n + m;i++){ dp[i] = cost(1, bg, i); if (p[i].second != p[i + 1].second){ solve(bg + 1, i); break; } } // cout << bg<< endl; // for (int i = 1;i <= n + m;i++) cout << dp[i] << ' '; // cout << endl; return dp[n + m]; }

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

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:47:6: warning: 'bg' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int bg;
      ^~
#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...