제출 #47038

#제출 시각아이디문제언어결과실행 시간메모리
47038SpaimaCarpatilorCultivation (JOI17_cultivation)C++17
0 / 100
34 ms576 KiB
#include<bits/stdc++.h> using namespace std; int N, R, C, x[309], y[309]; const int INF = 1e9 + 100; long long ans = 1LL << 60; set < int > sa, sb, sab; namespace ds { multiset < int > xs, dx; void init () { xs.clear (), dx.clear (); } void delDif (int x) { dx.erase (dx.find (x)); } void add (int x) { if (xs.find (x) != xs.end ()) xs.insert (x); else { xs.insert (x); auto it1 = xs.lower_bound (x), it2 = xs.upper_bound (x); if (it1 != xs.begin () && it2 != xs.end ()) it1 --, delDif ((*it2) - (*it1)), it1 ++; if (it1 != xs.begin ()) it1 --, dx.insert (x - (*it1)); if (it2 != xs.end ()) dx.insert ((*it2) - x); } } void del (int x) { if (xs.count (x) >= 2) xs.erase (xs.find (x)); else { auto it1 = xs.lower_bound (x), it2 = xs.upper_bound (x); if (it1 != xs.begin () && it2 != xs.end ()) it1 --, dx.insert ((*it2) - (*it1)), it1 ++; if (it1 != xs.begin ()) it1 --, delDif (x - (*it1)); if (it2 != xs.end ()) delDif ((*it2) - x); xs.erase (x); } } int maxDif () { if (dx.empty ()) return INF; return *(dx.rbegin ()); } int getA () { if (xs.empty ()) return INF; return (*xs.begin ()) - 1; } int getB () { if (xs.empty ()) return INF; return C - (*xs.rbegin ()); } } vector < pair < int, int > > events; void solve (int up, int down) { int minA = 0, minB = 0, minAB = 0; ds::init (); events.clear (); for (int i=1; i<=N; i++) { int lx = max (1, x[i] - up), dx = min (R, x[i] + down); events.push_back ({lx, -y[i]}); if (dx + 1 <= R) events.push_back ({dx + 1, y[i]}); } sort (events.begin (), events.end ()); for (int ii=0; ii<events.size (); ii++) { int jj = ii; while (jj < events.size () && events[jj].first == events[ii].first) { if (events[jj].second < 0) ds::add (-events[jj].second); else ds::del (events[jj].second); jj ++; } jj --; ///[ii, jj] minA = max (minA, ds::getA ()); minB = max (minB, ds::getB ()); minAB = max (minAB, ds::maxDif () - 1); /// ii = jj; } // printf ("(%d, %d) -> (%d, %d, %d)\n", up, down, minA, minB, minAB); long long curr = (long long) max (minA + minB, minAB) + up + down; if (curr < ans) ans = curr; } int main () { //freopen ("input", "r", stdin); //freopen ("output", "w", stdout); scanf ("%d %d\n", &R, &C); scanf ("%d", &N); for (int i=1; i<=N; i++) scanf ("%d %d", &x[i], &y[i]); for (int i=1; i<=N; i++) sa.insert (x[i] - 1), sb.insert (R - x[i]); for (int i=1; i<=N; i++) for (int j=i + 1; j<=N; j++) if (x[i] != x[j]) { int val = x[i] - x[j]; if (val < 0) val = -val; sab.insert (val - 1); } for (auto a : sa) { set < int > psb; for (auto b : sb) psb.insert (b); for (auto ab : sab) if (ab >= a) psb.insert (ab - a); for (auto b : psb) solve (a, b); } printf ("%lld\n", ans); return 0; }

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

cultivation.cpp: In function 'void solve(int, int)':
cultivation.cpp:94:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii=0; ii<events.size (); ii++)
                    ~~^~~~~~~~~~~~~~~
cultivation.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (jj < events.size () && events[jj].first == events[ii].first)
                ~~~^~~~~~~~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d\n", &R, &C);
 ~~~~~~^~~~~~~~~~~~~~~~~~~
cultivation.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N);
 ~~~~~~^~~~~~~~~~
cultivation.cpp:125:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &x[i], &y[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...
#Verdict Execution timeMemoryGrader output
Fetching results...