Submission #1324378

#TimeUsernameProblemLanguageResultExecution timeMemory
1324378quollcucumber`Garden (JOI23_garden)C++20
0 / 100
580 ms1114112 KiB
// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
#define int long long
using namespace std;
signed main() {
    int n, m, d;
    cin >> n >> m >> d;
    vector<int> grid[d * 4 + 15][d * 4 + 15];
    for(int i = 0; i < n; i ++) {
        int x, y;
        cin >> x >> y;
        for(int k = 0; k * d + x < d * 4 + 15; k++) {
            for(int l = 0; l * d + y < d * 4 + 15; l++) {
                grid[k * d + x][l * d + y ].push_back(i);
            }
        }
    }
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        for(int k = 0; k * d + x < d * 4 + 15; k++) {
            for(int l = 0; l < d * 4 + 15; l++) {
                grid[k * d + x][l].push_back(i + n);
            }
        }
        for(int k = 0; k < d * 4 + 15; k++) {
            for(int l = 0; l * d + y < d * 4 + 15; l++) {
                grid[k][d * l + y].push_back(i + n);
            }
        }
    }
    int nm = n + m;
    int minval = INT_MAX;
    for(int y = 0; y < 2 * d + 5; y++) {
        for(int length = 0; length < 2 * d + 5; length++) {
            map<int, int> amounts;
            int included = 0;
            int right = 0;
            //length is actually height oops.
            for(int i = 0; i < length; i++) {
                for(int k : grid[y + i][0]) {
                    amounts[k]++;
                    if(amounts[k] == 1) included++;
                }
            }
            while(included != nm) {
                if(right == d * 4 + 14) {
                    break;
                }
                right++;
                for(int i = 0; i < length; i++) {
                    for(int k : grid[y + i][right]) {
                        amounts[k]++;
                        if(amounts[k] == 1) included++;
                    }
                }
            }
            // if(included == nm) {
            //     minval = min(minval, length * (right + 1));
            //     for(int left = 1; left < 4 * d + 15; left++) {
            //         for(int i = 0; i < length; i++) {
            //             for(int k : grid[y + i][left -1]) {
            //                 amounts[k]--;
            //                 if(amounts[k] == 0) included--;
            //             }
            //         }
            //         while(included != nm) {
            //             if(right == d * 4 + 14) {
            //                 break;
            //             }
            //             right++;
            //             for(int i = 0; i < length; i++) {
            //                 for(int k : grid[y + i][right]) {
            //                     amounts[k]++;
            //                     if(amounts[k] == 1) included++;
            //                 }
            //             }
            //         }
            //         if(included == nm) {
            //             minval = min(minval, length * (right - left  + 1));
            //         }
            //     }
            // }
        }
    }
    cout<<minval<<'\n';
}
#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...