Submission #937813

#	Time	Username	Problem	Language	Result	Execution time	Memory
937813		anton	Garden (JOI23_garden)	C++17	14 / 100	3052 ms	20928 KiB

garden

#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;


}

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