#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;
}
Compilation message
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]);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
420 KB |
Output is correct |
| 2 |
Correct |
30 ms |
432 KB |
Output is correct |
| 3 |
Correct |
33 ms |
572 KB |
Output is correct |
| 4 |
Correct |
25 ms |
572 KB |
Output is correct |
| 5 |
Correct |
34 ms |
572 KB |
Output is correct |
| 6 |
Correct |
17 ms |
572 KB |
Output is correct |
| 7 |
Correct |
4 ms |
572 KB |
Output is correct |
| 8 |
Incorrect |
15 ms |
576 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
420 KB |
Output is correct |
| 2 |
Correct |
30 ms |
432 KB |
Output is correct |
| 3 |
Correct |
33 ms |
572 KB |
Output is correct |
| 4 |
Correct |
25 ms |
572 KB |
Output is correct |
| 5 |
Correct |
34 ms |
572 KB |
Output is correct |
| 6 |
Correct |
17 ms |
572 KB |
Output is correct |
| 7 |
Correct |
4 ms |
572 KB |
Output is correct |
| 8 |
Incorrect |
15 ms |
576 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
