Submission #850283

#	Time	Username	Problem	Language	Result	Execution time	Memory
850283		LucaIlie	Garden (JOI23_garden)	C++17	14 / 100	3054 ms	2856 KiB

garden

#include <bits/stdc++.h>

using namespace std;

const int MAX_D = 5000;

int frecvX[MAX_D], frecvY[MAX_D], f[MAX_D];
vector<int> vx[MAX_D];

int main() {
    int n, m, d;

    cin >> n >> m >> d;
    for ( int i = 0; i < n; i++ ) {
        int x, y;
        cin >> x >> y;
        frecvX[x]++;
        frecvY[y]++;
    }
    for ( int i = 0; i < m; i++ ) {
        int x, y;
        cin >> x >> y;
        vx[x].push_back( y );
        frecvY[y]++;
    }

    int minArea = d * d;
    for ( int l = 0; l < d; l++ ) {
        for ( int i = 0; i < d; i++ )
            f[i] = frecvY[i];

        int countX = 0;
        for ( int r = l; r < d; r++ ) {
            countX += frecvX[r];
            for ( int y: vx[r] )
                f[y]--;

            int max0 = 0, crt0 = 0;
            for ( int i = 0; i < d; i++ ) {
                if ( f[i] == 0 )
                    crt0++;
                else
                    crt0 = 0;
                max0 = max( max0, crt0 );
            }
            int pref0 = 0;
            while ( pref0 < d && f[pref0] == 0 )
                pref0++;
            int suf0 = 0;
            while ( suf0 < n && f[d - 1 - suf0] == 0 )
                suf0++;
            max0 = max( max0, min( d, suf0 + pref0 ) );

            if ( countX >= n )
                minArea = min( minArea,  (r - l + 1) * (d - max0) );
        }


        for ( int r = 0; r < l; r++ ) {
            countX += frecvX[r];
            for ( int y: vx[r] )
                f[y]--;

            int max0 = 0, crt0 = 0;
            for ( int i = 0; i < d; i++ ) {
                if ( f[i] == 0 )
                    crt0++;
                else
                    crt0 = 0;
                max0 = max( max0, crt0 );
            }
            int pref0 = 0;
            while ( pref0 < d && f[pref0] == 0 )
                pref0++;
            int suf0 = 0;
            while ( suf0 < n && f[d - 1 - suf0] == 0 )
                suf0++;
            max0 = max( max0, min( d, suf0 + pref0 ) );

            if ( countX >= n )
                minArea = min( minArea,  (d - l + r + 1) * (d - max0) );
        }
    }

    cout << minArea;

    return 0;
}

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