Submission #819261

#	Time	Username	Problem	Language	Result	Execution time	Memory
819261		tengiz05	Garden (JOI23_garden)	C++17	30 / 100	3078 ms	4180 KiB

garden

#include <bits/stdc++.h>

using i64 = long long;
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, D;
    cin >> n >> m >> D;
    
    vector<int> p(n), q(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i] >> q[i];
    }
    
    vector<int> r(m), s(m);
    for (int i = 0; i < m; i++) {
        cin >> r[i] >> s[i];
    }
    
    deque<pair<int, int>> g;
    for (int i = 0; i < m; i++) {
        g.push_back(pair(r[i], s[i]));
    }
    
    sort(g.begin(), g.end());
    
    // deque<int> P(m);
    // iota(P.begin(), P.end(), 0);
    // sort(P.begin(), P.end(), [&](int i, int j) {
        // return r[i] < r[j];
    // });
    
    int ans = 1E9;
    
    for (int a = 0; a < D; a++) {
        while (g[0].first < a) {
            g.push_back({g[0].first + D, g[0].second});
            g.pop_front();
        }
        for (int b = 0; b < D; b++) {
            int X = a, Y = b;
            for (int i = 0; i < n; i++) {
                if (p[i] < a) X = max(X, p[i] + D);
                else X = max(X, p[i]);
                if (q[i] < b) Y = max(Y, q[i] + D);
                else Y = max(Y, q[i]);
            }
            // cout << a << " " << b << " " << X << " " << Y << "\n";
            ans = min(ans, (max(X, g.back().first) - a + 1) * (Y - b + 1));
            for (int i = m - 1; i >= 0; i--) {
                if (g[i].second < b) Y = max(Y, g[i].second + D);
                else Y = max(Y, g[i].second);
                if (i == 0) {
                    ans = min(ans, (X - a + 1) * (Y - b + 1));
                } else {
                    ans = min(ans, (max(X, g[i - 1].first) - a + 1) * (Y - b + 1));
                }
            }
        }
    }
    
    cout << ans << "\n";
    
    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