제출 #42989

#제출 시각아이디문제언어결과실행 시간메모리
42989alenam0161전선 연결 (IOI17_wiring)C++14
13 / 100
68 ms10800 KiB
#include "wiring.h" #include <iostream> #include <algorithm> using namespace std; vector<long long> pre, suf; vector<pair<long long, int>> all; int n; long long pre_gum(int l, int r) { if (l > r)return 0; if (l == 0) { return pre[r] - (r - l + 1)*all[0].first; } return pre[r] - pre[l - 1] - all[l].first * (r - l + 1); } long long suf_gum(int l, int r) { if (l > r)return 0; return suf[l] - suf[r + 1] - (all[n - 1].first - all[r].first) * (r - l + 1); } long long sum(int l, int mid, int r) { return suf_gum(l, mid) + pre_gum(mid + 1, r) + 1ll * max(mid - l + 1, r - mid)*(all[mid + 1].first - all[mid].first); } long long min_total_length(std::vector<int> r, std::vector<int> b) { for (int to : r)all.push_back({ to,1 }); for (int to : b)all.push_back({ to,2 }); int n = all.size(); ::n = n; sort(all.begin(), all.end()); vector<int> left(n + 1, 0); for (int i = 0; i < n; ++i) { if (i == 0 || (all[i].second != all[i - 1].second)) { left[i] = i; } else left[i] = left[i - 1]; } pre.resize(n + 5, 0); suf.resize(n + 5, 0); for (int i = 0; i < n; ++i) { pre[i] = (i == 0 ? 0 : pre[i - 1]) + all[i].first; // cout << "pre[" << i << "] = " << pre[i] << endl; } for (int i = n - 1; i >= 0; i--) { suf[i] = (i == n - 1 ? 0 : suf[i + 1]) + all[n - 1].first - all[i].first; } vector<long long> dp(n + 5, (long long)1e18); int pos = 0; long long mn; int lf; for (int i = 0; i < n; ++i) { if (left[i] == 0)continue; if (left[i] == i) { mn = dp[i - 1]; lf = left[i] - 1; mn = dp[lf]; for (int j = lf; j >= left[lf]; --j) { if (j == 0)mn = 0; else mn = min(mn, dp[j - 1]); if (mn + sum(j, lf, i) < dp[i]) { pos = j; dp[i] = mn + sum(j, lf, i); } } } else { if (pos == left[lf])dp[i] = mn + sum(left[lf], lf, i); else { if (i - lf == lf - pos + 1) { if (sum(pos, lf, i) + mn < sum(pos - 1, lf, i) + min(mn, dp[pos - 2])) { pos--; mn = min(mn, dp[pos - 2]); } dp[i] = mn + sum(pos, lf, i); } else { dp[i] = mn + sum(pos, lf, i); } } } } return dp[n - 1]; }

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

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:75:22: warning: 'lf' may be used uninitialized in this function [-Wmaybe-uninitialized]
      dp[i] = mn + sum(pos, lf, 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...