Submission #1024964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024964		Alihan_8	Garden (JOI23_garden)	C++17	6 / 100	3064 ms	24216 KiB

garden

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, d; cin >> n >> m >> d;

    vector <int> P(n), Q(n), R(m), S(m);

    for ( int i = 0; i < n; i++ ){
        cin >> P[i] >> Q[i];
    }

    for ( int i = 0; i < m; i++ ){
        cin >> R[i] >> S[i];
    }

    { // sorting
        vector <int> p_(m);

        iota(all(p_), 0);

        sort(all(p_), [&](int &u, int &v){
             return R[u] < R[v];
        });

        auto _R = R, _S = S;

        for ( int i = 0; i < m; i++ ){
            R[i] = _R[p_[i]];
            S[i] = _S[p_[i]];
        }

        p_ = vector <int> (n);

        iota(all(p_), 0);

        sort(all(p_), [&](int &u, int &v){
             return P[u] < P[v];
        });

        auto _P = P, _Q = Q;

        for ( int i = 0; i < n; i++ ){
            P[i] = _P[p_[i]];
            Q[i] = _Q[p_[i]];
        }
    }
    
    int opt = 1e9;
    
    for ( int x1 = 0; x1 < d; x1++ ){
		for ( int x2 = x1; x2 < d; x2++ ){
			for ( int y1 = 0; y1 < d * 2; y1++ ){
				for ( int y2 = y1; y2 < d * 2; y2++ ){
					bool ok = true;
					
					for ( int i = 0; i < n; i++ ){
						bool tmp = false;
						
						for ( auto t: {0LL, d} ){
							tmp |= (x1 <= P[i] && x2 >= P[i]) & (y1 <= Q[i] + t && y2 >= Q[i] + t);
						}
						
						ok &= tmp;
					}
					
					for ( int j = 0; j < m; j++ ){
						bool tmp = false;
						
						for ( auto t: {0LL, d} ){						
							tmp |= (x1 <= R[j] && x2 >= R[j]) | (y1 <= S[j] + t && y2 >= S[j] + t);
						}
						
						ok &= tmp;
					}
				
					if ( ok > 0 ){
						chmin(opt, (x2 - x1 + 1) * (y2 - y1 + 1));
					}
				}
			}
		}
	}
	
	cout << opt;

    cout << '\n';
}

• Subtask 1: 0 / 15
• Subtask 2: 6 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25