// vaziat meshki-ghermeze !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<int, int> pii;
const ll Mod = 1000000007LL;
const int N = 3e2 + 10;
const int Inf = 2'000'000'001;
const ll Log = 30;
int n, R, C;
pii A[N];
// 0, x, y -> C + R < x -> y
// 1, x, y -> C < x -> y
// 2, x, y -> R < x -> y
typedef pii con;
typedef pair<con, int> Query;
vector<Query> Q, TQ, V0, V1;
typedef pair<con, con> iff;
vector< pair<iff, int> > cons;
bool Better(con A, con B){
if(A.F != B.F)
return false;
return A.S >= B.S;
}
bool Sat(con A, int i, int j){
if(A.F == 0)
return i + j < A.S;
if(A.F == 1)
return i < A.S;
return j < A.S;
}
void Check(int l, int r){
int ln = r - l - 1;
vector<int> V;
for(int k = 1; k <= n; k++){
if(l < A[k].F && A[k].F < r)
V.pb(A[k].S);
}
sort(all(V));
int sz = Q.size();
vector< pair<con, int> > tmp;
if(!V.empty() && V[0] > 1)
tmp.pb({{1, V[0] - 1}, ln});
if(!V.empty() && V.back() < C)
tmp.pb({{2, C - V.back()}, ln});
for(int i = 0; i + 1 < (int) V.size(); i++){
if(0 < V[i + 1] - V[i] - 1)
tmp.pb({{0, V[i + 1] - V[i] - 1}, ln});
}
if(V.empty())
tmp.pb({{1, C}, ln});
sort(all(tmp));
for(int i = 0; i < (int) tmp.size(); i++)
if((i + 1 == (int) tmp.size()) || (!Better(tmp[i + 1].F, tmp[i].F)) )
Q.pb(tmp[i]);
for(int i = sz; i < (int) Q.size(); i++)
TQ.pb(Q[i]);
// Q.resize(sz);
}
int ans[N][N]; // C R
pii Inter(pii A, pii B){ return pii(max(A.F, B.F), min(A.S, B.S)); }
pii Inter(con c, int v){
if(c.F == 0){
if(v > c.S)
return pii(0, v + 1);
return pii(v + 1, 0);
} else if(c.F == 1){
return pii(0, c.S);
}
return pii((v - c.S) + 1, v + 1);
}
pii Inter(iff c, int v){ return Inter(Inter(c.F, v), Inter(c.S, v)); }
vector<iff> act;
bool Valid(int v){
// vector<int> mk(C + 2, 0);
v = min(C - 1 + C - 1, v);
for(int i = 0; i < C; i++)
for(int j = 0; j < C; j++)
if(i + j <= v && ans[i][j] == 0)
return true;
return false;
// for(auto fi : act){
// pii X = Inter(fi, v);
// X.S = min(X.S, C + 1);
// X.F = max(X.F, 0);
// if(X.F >= X.S) continue;
// for(int i = X.F; i < X.S; i++) mk[i] = 1;
// }
// for(auto c : mk)
// if(c == 0)
// return true;
// return false;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> R >> C >> n;
for(int i = 1; i <= n; i++){
cin >> A[i].F >> A[i].S;
}
sort(A + 1, A + n + 1);
// vector<int> V;
// sort(all(V));
// for(int i = 1; i <= n; i++) V.pb(A[i].S);
// int mn_S = 0;
// for(int i = 0; i < n; i++)
// mn_S = max(mn_S, V[i + 1] - V[i] - 1);
// Check(0, R + 1);
// int mx = (A[1].F - 1) + (R - A[n].F);
Check(0, R + 1);
for(auto &[cn, sm] : Q)
sm = Inf;
TQ.clear();
int sz = Q.size();
for(int i = 1; i <= n; i++)
Check(0, A[i].F);
Q.resize(sz);
V0 = TQ; TQ.clear();
for(int i = 1; i <= n; i++)
Check(A[i].F, R + 1);
Q.resize(sz);
V1 = TQ; TQ.clear();
for(auto [c1, v1] : V0)
for(auto [c2, v2] : V1)
cons.pb({{min(c1, c2), max(c1, c2)}, v1 + v2});
Q.resize(sz);
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
if(A[j].F - 1 > A[i].F)
Check(A[i].F, A[j].F);
for(auto [c1, v1] : Q)
cons.pb({{c1, c1}, v1});
sort(all(cons), [&](auto e1, auto e2){
return e1.S > e2.S;
});
int ANS = R + C;
cons.pb({{{0, 0}, {0, 0}}, 0});
for(auto [fi, v] : cons){
// debug(v);
// for(int i = 0; i < C; i++){
// for(int j = 0; j < C; j++)
// if(!ans[i][j])
// ANS = min(ANS, i + j + v);
// }
int L = -1, R = C + C;
int mid;
while(L + 1 < R){
mid = (L + R) >> 1;
if(Valid(mid)) R = mid;
else L = mid;
}
ANS = min(ANS, R + v);
auto [c1, c2] = fi;
for(int i = 0; i < C; i++)
for(int j = 0; j < C; j++)
if(Sat(c1, i, j) && Sat(c2, i, j))
ans[i][j] = 1;
// act.pb(fi);
}
cout << ANS << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1484 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1484 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
