Submission #414304

#TimeUsernameProblemLanguageResultExecution timeMemory
414304amoo_safarCultivation (JOI17_cultivation)C++17
15 / 100
1086 ms15044 KiB
// 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, j = v; i < C; i++, j--) if(0 <= j && j < C && 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); // int CC = C + C; // for(int i = 0; i < C; i++){ // for(int j = 0; j < C; j++) // if(!ans[i][j]) // // CC = min(CC, i + j); // ANS = min(ANS, i + j + v); // } int L = -1, Rb = C + C - 1; int mid; while(L + 1 < Rb){ mid = (L + Rb) >> 1; if(Valid(mid)) Rb = mid; else L = mid; } if(Rb != C + C - 1) ANS = min(ANS, Rb + 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 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...