제출 #937813

#제출 시각아이디문제언어결과실행 시간메모리
937813antonGarden (JOI23_garden)C++17
14 / 100
3052 ms20928 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;

signed main(){
    cin>>n>>m>>d;

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

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



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

    int res= 1e18;

    for(int i = 0; i<d; i++){
        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(int j = 0; j<d; j++){
            //cout<<i<<" "<<j<<endl;
            set<pii> vm;
            set<pii> hm;
            for(auto e: vecm){
                if(e.first<i){
                    e.first+=d;
                }
                if(e.second<j){
                    e.second+=d;
                }
                vm.insert(e);
            }
            int h = max(vn.back(), (--vm.end())->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());
                hm.insert({last.second, last.first});
                
                h= vn.back();
                if(vm.size()>0){
                    h =max(h, (--vm.end())->first);
                }
                w= hn.back();
                if(hm.size()>0){
                    w= max(w, (--hm.end())->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...