Submission #965255

#	Time	Username	Problem	Language	Result	Execution time	Memory
965255		Darren0724	Garden (JOI23_garden)	C++17	30 / 100	3079 ms	12696 KiB

garden

#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));
    if(v.size()==1)return (r-l+1);
    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;
}

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