Submission #937817

#TimeUsernameProblemLanguageResultExecution timeMemory
937817antonGarden (JOI23_garden)C++17
14 / 100
3031 ms16756 KiB
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
int n, m, d;

vector<pii> vecn;
vector<pii> vecm;


set<int> h_important;
set<int> w_important;
signed main(){
    cin>>n>>m>>d;

    for(int i = 0; i<n; i++){
        pii v;
        cin>>v.second>>v.first;
        vecn.push_back(v);
        h_important.insert(v.first);
        w_important.insert(v.second);
    }
    for(int i = 0; i<m; i++){
        pii v;
        cin>>v.second>>v.first;
        vecm.push_back(v);
        
        h_important.insert(v.first);
        w_important.insert(v.second);
    }

    sort(vecn.begin(), vecn.end());



    deque<int> vn;
    for(auto e: vecn){
        vn.push_back(e.first);
    }

    int res= 1e18;

    for(auto i: h_important){
        deque<int> hn;
        auto cmp = [&](pii&a, pii& b){
            return a.second<b.second;
        };
        sort(vecn.begin(), vecn.end(), cmp);
        for(auto e: vecn){
            hn.push_back(e.second);
        }

        for(auto j: w_important){
            //cout<<i<<" "<<j<<endl;
            vector<pii> vm;
            for(auto e: vecm){
                if(e.first<i){
                    e.first+=d;
                }
                if(e.second<j){
                    e.second+=d;
                }
                vm.push_back(e);
            }
            sort(vm.begin(), vm.end());
            int h = max(vn.back(), vm.back().first);
            int w= hn.back();
            
            res= min(res, (h-i+1)*(w-j+1));
            
            while(vm.size()>0){
                pii last=*(--vm.end());
                vm.erase(--vm.end());
            
                w= max(w, last.second);
                h= vn.back();
                if(vm.size()>0){
                    h =max(h, vm.back().first);
                }
                //cout<<"coords "<<i<<" "<<j<<" "<<h<<" "<<w<<endl;
                res= min(res, (h-i+1)*(w-j+1));
            }

            /*cout<<"vn"<<endl;
            for(auto e: vn){
                cout<<e<<" ";
            }
            cout<<endl;
            cout<<"hn"<<endl;
            for(auto e: hn){
                cout<<e<<" ";
            }
            cout<<endl;*/
            
            while(hn.size()>0 && hn.front()==j){
                int cur= hn.front();
                hn.pop_front();
                hn.push_back(cur+d);
            }
        }

        while(vn.size()>0 && vn.front()==i){
            int cur= vn.front();
            vn.pop_front();
            vn.push_back(cur+d);
        }
    }

    cout<<res<<endl;


}
#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...