제출 #418846

#제출 시각아이디문제언어결과실행 시간메모리
418846Kevin_Zhang_TWCultivation (JOI17_cultivation)C++17
0 / 100
1 ms204 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb emplace_back #define AI(i) begin(i), end(i) template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); } template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); } #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void kout() { cerr << endl; } template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); } template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; } #else #define DE(...) 0 #define debug(...) 0 #endif const int MAX_N = 305; #define int ll const int inf = 1ll << 55; int R, C, n; vector<pair<int,int>> loc; int cal_up(int ul) { int dnmn = 0; { vector<int> ys; for (auto [x, y] : loc) ys.pb(y - ul); sort(AI(ys)); int lst_end = 0; for (int y : ys) { chmax(dnmn, y - 1 - lst_end); lst_end = y + ul; } chmax(dnmn, C - lst_end); } vector<vector<tuple<int,int,int>>> op2, must; vector<int> sep; DE(ul); auto all_op = [&]() { op2.pb(); must.pb(); sort(AI(loc)); for (int i = 0;i < n;++i) { auto [x, y] = loc[i]; DE(x, y); auto segmx = [&](int l, int r, int v) { chmax(l, dnmn); chmin(r, C); if (l > r) return; DE("segmx", l, r, v - x - 1); sep.pb(l), sep.pb(r+1); op2.back().pb(l, r+1, v - x - 1); }; auto allmx = [&](int l, int r, int v) { chmax(l, dnmn); chmin(r, C); if (l > r) return; sep.pb(l), sep.pb(r+1); DE("mustmx", l, r, v - x - 1); must.back().pb(l, r+1, v - x - 1); }; set<int> ys; ys.insert(-inf); ys.insert(inf); int nl = 0, nr = C; for (int j = i+1;j < n;++j) { auto [cx, cy] = loc[j]; if (cx == x) continue; if (cy <= y) chmax(nl, cy + 1); if (cy >= y) chmin(nr, cy - ul - 1); DE(cx, cy); auto it = ys.lower_bound(cy); int ly = *prev(it), ry = *it; ys.insert(cy); int s = -1, e = min(C - ly, ry - ul - 1 - ly); if (y <= ly || y >= ry) continue; if (cy >= y) s = max<ll>(0, cy - ul - y); else s = max<ll>(0, y - ul - cy); segmx(s, e, cx); } DE(nl, nr); if (nl == 0) allmx(0, C, R + 1); else if (nl <= nr) allmx(0, nr - nl, R + 1); } DE(op2.size()); for (auto [l, r, v] : op2.back()) { DE(l, r, v); } }; all_op(); for (auto &[x, y] : loc) x = R - x + 1; all_op(); for (auto &[x, y] : loc) x = R - x + 1; sep.pb(C+1); sort(AI(sep)); sep.erase(unique(AI(sep)), end(sep)); priority_queue<pair<int,int>> pq[2], pq2[2]; sort(AI(op2[0])); sort(AI(op2[1])); sort(AI(must[0])); sort(AI(must[1])); int h[2]{}, h2[2]{}; int res = inf; for (int i = 0;i+1 < sep.size();++i) { auto add_in = [&](auto &pq, auto &op, int &i) { for (;i < op.size();++i) { auto [l, r, v] = op[i]; if (l > sep[i]) break; pq.emplace(v, r); } }; auto pops = [&](auto &pq) -> ll{ while (pq.size() && pq.top().second <= sep[i]) pq.pop(); return pq.size() ? pq.top().first : 0; }; add_in(pq[0], op2[0], h[0]); add_in(pq[1], op2[1], h[1]); add_in(pq2[0], must[0], h2[0]); add_in(pq2[1], must[1], h2[1]); chmin(res, sep[i] + ul + max({pops(pq[0]), pops(pq[1]), pops(pq2[0]) + pops(pq2[1])})); } DE(ul, res); return res; } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> R >> C >> n; loc.resize(n); for (auto &[x, y] : loc) { cin >> x >> y; } sort(AI(loc)); int res = inf; vector<int> ys; for (auto [x, y] : loc) ys.pb(y); // location should be the same for (int y : ys) { chmin(res, cal_up(y - 1)); // TODO //break; } cout << res << '\n'; }

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

cultivation.cpp: In function 'll cal_up(ll)':
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cultivation.cpp:43:2: note: in expansion of macro 'DE'
   43 |  DE(ul);
      |  ^~
cultivation.cpp: In lambda function:
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cultivation.cpp:52:4: note: in expansion of macro 'DE'
   52 |    DE(x, y);
      |    ^~
cultivation.cpp: In lambda function:
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cultivation.cpp:57:5: note: in expansion of macro 'DE'
   57 |     DE("segmx", l, r, v - x - 1);
      |     ^~
cultivation.cpp: In lambda function:
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cultivation.cpp:67:5: note: in expansion of macro 'DE'
   67 |     DE("mustmx", l, r, v - x - 1);
      |     ^~
cultivation.cpp: In lambda function:
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cultivation.cpp:83:5: note: in expansion of macro 'DE'
   83 |     DE(cx, cy);
      |     ^~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cultivation.cpp:93:4: note: in expansion of macro 'DE'
   93 |    DE(nl, nr);
      |    ^~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cultivation.cpp:100:3: note: in expansion of macro 'DE'
  100 |   DE(op2.size());
      |   ^~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cultivation.cpp:102:4: note: in expansion of macro 'DE'
  102 |    DE(l, r, v);
      |    ^~
cultivation.cpp:101:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  101 |   for (auto [l, r, v] : op2.back()) {
      |             ^~~~~~~~~
cultivation.cpp: In function 'll cal_up(ll)':
cultivation.cpp:127:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  for (int i = 0;i+1 < sep.size();++i) {
      |                 ~~~~^~~~~~~~~~~~
cultivation.cpp: In instantiation of 'cal_up(ll)::<lambda(auto:23&, auto:24&, ll&)> [with auto:23 = std::priority_queue<std::pair<long long int, long long int> >; auto:24 = std::vector<std::tuple<long long int, long long int, long long int> >; ll = long long int]':
cultivation.cpp:141:29:   required from here
cultivation.cpp:129:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |    for (;i < op.size();++i) {
      |          ~~^~~~~~~~~~~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cultivation.cpp:150:2: note: in expansion of macro 'DE'
  150 |  DE(ul, res);
      |  ^~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...