제출 #1207948

#제출 시각아이디문제언어결과실행 시간메모리
1207948mychecksedadCultivation (JOI17_cultivation)C++20
30 / 100
281 ms1476 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n, m, w; array<int, 2> a[N]; void solve(){ cin >> n >> m >> w; vector<array<int, 2>> ST; int mn = n, mx = 1; for(int i = 1; i <= w; ++i){ cin >> a[i][0] >> a[i][1]; mn = min(mn, a[i][0]); mx = max(mx, a[i][0]); } for(int i = 1; i <= w; ++i){ ST.pb({max(1, a[i][0] - (mn - 1)), min(n, a[i][0] + (n - mx))}); } vi U, D; for(auto [l, r]: ST){ U.pb(l - 1); D.pb(n - r); for(auto [l2, r2]: ST){ if(r < l2 || r2 < l){ if(r < l2){ D.pb(l2 - r - 1); U.pb(l2 - r - 1); }else{ D.pb(l - r2 - 1); U.pb(l - r2 - 1); } } } } sort(all(U)); sort(all(D)); U.erase(unique(all(U)), U.end()); D.erase(unique(all(D)), D.end()); ll ans = 1e18; for(ll u: U){ u = u + (mn - 1); for(ll d: D){ d = d + (n - mx); // cerr << u << ' ' << d << '\n'; vector<array<ll, 3>> A, B; vi X; for(int i = 1; i <= w; ++i){ A.pb({a[i][0] - u, a[i][0] + d, a[i][1]}); B.pb({a[i][0] + d, a[i][0] - u, a[i][1]}); X.pb(a[i][0] - u); X.pb(a[i][0] + d + 1); // cerr << A.back()[0] << ' ' << A.back()[1] << ' '<< A.back()[2] << '\n'; } X.pb(1); X.pb(n); sort(all(A)); sort(all(B)); sort(all(X)); X.erase(unique(all(X)), X.end()); int ptr = 0, ptr2 = 0; ll L = 0, R = 0, D = 0; multiset<ll> Y; // active columns for(int x_pos: X){ if(x_pos < 1 || x_pos > n) continue; // cerr << l << ' ' << r << ' ' << col << '\n'; while(ptr < B.size() && B[ptr][0] < x_pos){ Y.erase(Y.find(B[ptr][2])); ++ptr; } while(ptr2 < A.size() && A[ptr2][0] <= x_pos){ Y.insert(A[ptr2][2]); ++ptr2; } if(Y.empty()){ L = INT_MAX - d - u; R = D = 0; break; } L = max(L, (*Y.begin()) - 1); R = max(R, m - (*prev(Y.end()))); int last_val = (*Y.begin()); for(auto val: Y){ D = max(D, val - last_val - 1); last_val = val; } } // cerr << L << ' ' << R << ' ' << D << ' ' << d << ' ' << u << ' ' << L + R + max(0, D - L - R) + d + u << '\n'; ans = min(ans, L + R + max(0ll, D - L - R) + d + u); } } cout << ans; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\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...