제출 #965260

#제출 시각아이디문제언어결과실행 시간메모리
965260Darren0724Garden (JOI23_garden)C++17
30 / 100
3058 ms12468 KiB
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define LCBorz ios_base::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
const int N=500005;
const int D=205;
const int INF=1e9;
const int lim=1000;
int n,m,d;
vector<pair<int,int>> a(N),b(N);
int solve(int l,int r){
    vector<int> v;
    for(int i=0;i<n;i++){
        if((a[i].x<l&&a[i].x+d>r)||l>a[i].x+d||r<a[i].x){
            return INF;
        }
        v.push_back(a[i].y);
    }
    for(int i=0;i<m;i++){
        if((b[i].x<l&&b[i].x+d>r)||l>b[i].x+d||r<b[i].x){
            v.push_back(b[i].y);
        }
    }
    sort(all(v));
    int sz=v.size();
    int mx=(v[0]+d-v[sz-1]-1);
    for(int i=1;i<sz;i++){
        mx=max(mx,v[i]-v[i-1]-1);
    }
    int ans=(d-mx)*(r-l+1);
    //cout<<l<<' '<<r<<' '<<ans<<endl;
    return ans;
}
int32_t main(){
    LCBorz;
    cin>>n>>m>>d;
    for(int i=0;i<n;i++){
        cin>>a[i].x>>a[i].y;
    }
    for(int i=0;i<m;i++){
        cin>>b[i].x>>b[i].y;
    }
    int ans=INF;
    for(int i=0;i<d*2;i++){
        for(int j=i;j<d*2;j++){
            ans=min(ans,solve(i,j));
        }
    }
    cout<<ans<<endl;
    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...