Submission #1167596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167596		acoatoitgs	Garden (JOI23_garden)	C++20	6 / 100	3093 ms	8256 KiB

garden

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

#define ll long long
#define pb push_back
#define m_pi 2 * acos(0.0)
#define all(a) (a).begin(), (a).end()
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
void solve();

constexpr bool isTc = 0;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    if (isTc)
    {
        int T;
        cin >> T;
        while (T--)
        {
            solve();
        }
    }
    else
        solve();
    return 0;
}

/*######################################*/

void solve()
{
    ll N, M, D;
    cin >> N >> M >> D;
    vector<ll> Ax(N), Ay(N), Bx(M), By(M);

    for(int i = 0; i < N; i++)
        cin >> Ax[i] >> Ay[i];

    for(int i = 0; i < M; i++)
        cin >> Bx[i] >> By[i];

    //Suppose lower left point is N
    ll best = D*D;
    for(ll point = 0; point < N; point++)
    {
        ll rx = Ax[point];
        ll ry = Ay[point];

        ll dx = 1, dy = 1;

        for(ll i = 0; i < N; i++)
        {
            dx = max(dx, (Ax[i] < rx ? D+Ax[i] : Ax[i])-rx+1);
            dy = max(dy, (Ay[i] < ry ? D+Ay[i] : Ay[i])-ry+1);
        }
        for(ll i = 0; i < M; i++)
        {
            ll des_x = (Bx[i] < rx ? D+Bx[i] : Bx[i])-rx+1;
            ll des_y = (By[i] < ry ? D+By[i] : By[i])-ry+1;

            if(des_x <= dx || des_y <= dy) continue;
            //suboptimal
            if(des_x*dy < des_y*dx) dx = des_x;
            else dy = des_y;
        }
        best = min(best, dx*dy);
    }

    //Suppose lower right point is N
    for(ll point = 0; point < N; point++)
    {
        ll rx = Ax[point];
        ll ry = Ay[point];

        ll dx = 1, dy = 1;

        for(ll i = 0; i < N; i++)
        {
            dx = max(dx, rx-(Ax[i] <= rx ? Ax[i] : Ax[i]-D)+1);
            dy = max(dy, (Ay[i] < ry ? D+Ay[i] : Ay[i])-ry+1);
        }

        for(ll i = 0; i < M; i++)
        {
            ll des_x = rx-(Bx[i] <= rx ? Bx[i] : Bx[i]-D)+1;
            ll des_y = (By[i] < ry ? D+By[i] : By[i])-ry+1;

            if(des_x <= dx || des_y <= dy) continue;
            //suboptimal
            if(des_x*dy < des_y*dx) dx = des_x;
            else dy = des_y;
        }
        best = min(best, dx*dy);
    }

    cout << best << "\n";
}

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