제출 #453526

#제출 시각아이디문제언어결과실행 시간메모리
453526nonsensenonsense1Palembang Bridges (APIO15_bridge)C++17
0 / 100
1 ms204 KiB
#include <cstdio> #include <vector> const int N = 1000000000; int k, n; std::vector<std::pair<int, int> > a; long long test2(int x, int y) { long long s = 0; for (int i = 0; i < (int)a.size(); ++i) s += std::min(std::max(a[i].first - x, 0) + std::max(x - a[i].second, 0), std::max(a[i].first - y, 0) + std::max(y - a[i].second, 0)); return s; } long long test1(int x) { int l = x, r = N, opt; while (l <= r) { int m = l + r >> 1; if (test2(x, m) <= test2(x, m + 1)) { opt = m; r = m - 1; } else l = m + 1; } return test2(x, opt); } long long test0() { int l = 0, r = N, opt; while (l <= r) { int m = l + r >> 1; if (test1(m) <= test1(m + 1)) { opt = m; r = m - 1; } else l = m + 1; } return test1(opt); } long long test(int x) { long long r = ~((long long)1 << 63); for (int i = 0; i < (int)a.size(); ++i) { r = std::min(r, test2(x, a[i].first)); r = std::min(r, test2(x, a[i].first - 1)); r = std::min(r, test2(x, a[i].first + 1)); r = std::min(r, test2(x, a[i].second)); r = std::min(r, test2(x, a[i].second - 1)); r = std::min(r, test2(x, a[i].second + 1)); } return r; } int main() { long long ans = 0; scanf("%d%d", &k, &n); for (int i = 0; i < n; ++i) { char type_from, type_to; int from, to; scanf(" %c%d %c%d", &type_from, &from, &type_to, &to); if (from > to) std::swap(from, to); ans += to - from; if (type_from != type_to) { a.push_back(std::make_pair(from, to)); ++ans; } } long long mn = ~((long long)1 << 63); for (int i = 0; i < 100; ++i) mn = std::min(mn, test2(-N, i)); printf("%lld\n", ans + mn * 2); return 0; if (k == 1) printf("%lld\n", ans + test1(-N) * 2); else { long long r = ~((long long)1 << 63); for (int i = 0; i < (int)a.size(); ++i) { r = std::min(r, test(a[i].first)); r = std::min(r, test(a[i].second)); } printf("%lld\n", ans + r * 2); } return 0; }

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

bridge.cpp: In function 'long long int test1(int)':
bridge.cpp:20:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |   int m = l + r >> 1;
      |           ~~^~~
bridge.cpp: In function 'long long int test0()':
bridge.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int m = l + r >> 1;
      |           ~~^~~
bridge.cpp: In function 'int main()':
bridge.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d%d", &k, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~
bridge.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf(" %c%d %c%d", &type_from, &from, &type_to, &to);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'long long int test1(int)':
bridge.cpp:27:14: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |  return test2(x, opt);
      |         ~~~~~^~~~~~~~
bridge.cpp: In function 'long long int test0()':
bridge.cpp:41:14: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |  return test1(opt);
      |         ~~~~~^~~~~
#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...