Submission #810888

#	Time	Username	Problem	Language	Result	Execution time	Memory
810888		YesPy	Garden (JOI23_garden)	C++17	6 / 100	187 ms	41872 KiB

garden

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(nullptr);
#define ln '\n'
#define nwln cout<<ln;

using namespace std;

using oo = bool;

#define mins(i, j) (i = min(i, j))
#define fri(i,a,b) for(int i=(a); i<(b); ++i)

const int INF = 1001002003;

int N, M, D, T, ans = INF;
bitset<5001> mtx[20][20];
bitset<5001> dp[400][400];

inline int comp(int x, int y) { return x*T + y; }

int main()
{
	fastio
	cin>>N>>M>>D, T = D<<1;

	fri(i,0,N) {
		int P, Q;
		cin>>P>>Q;

		fri(x,0,2) {
			fri(y,0,2) {
				mtx[P+x*D][Q+y*D][i] = 1;
			}
		}
	}

	fri(i,N,N+M) {
		int R, S;
		cin>>R>>S;
		
		fri(y,0,T) {
			mtx[R][y][i] = 1;
			mtx[R+D][y][i] = 1;
		}

		fri(x,0,T) {
			mtx[x][S][i] = 1;
			mtx[x][S+D][i] = 1;
		}
	}

	// fri(i,0,T) {
	// 	fri(j,0,T) cout<<mtx[i][j]<<" ";
	// 	nwln
	// }

	// nwln

	fri(i1,0,T) {
		fri(j1,0,T) {
			fri(i2,i1,T) {
				fri(j2,j1,T) {
					int i0 = comp(i1, j1), j0 = comp(i2, j2);
					
					if((i2==i1) && (j2==j1)) {
						dp[i0][j0] = mtx[i2][j2];
					} else if(i2 == i1) {
						dp[i0][j0] = dp[i0][comp(i2, j2-1)];
						dp[i0][j0] |= mtx[i2][j2];
					} else if(j2 == j1) {
						dp[i0][j0] = dp[i0][comp(i2-1, j2)];
						dp[i0][j0] |= mtx[i2][j2];
					} else {
						dp[i0][j0] = mtx[i2][j2];
						dp[i0][j0] |= dp[i0][comp(i2-1, j2)];
						dp[i0][j0] |= dp[i0][comp(i2, j2-1)];
					}

					// cout<<"dp["<<i1<<", "<<j1<<"]["<<i2<<", "<<j2<<"] = "<<dp[i0][j0]<<ln;
				}
			}
		}
	}

	// nwln

	fri(i1,0,T) {
		fri(j1,0,T) {
			fri(i2,i1,T) {
				fri(j2,j1,T) {
					int x = comp(i1, j1), y = comp(i2, j2);
					
					oo flag = true;
					fri(z,0,N+M) flag &= (dp[x][y][z] == 1);

					// if(flag == true) {
					// 	cout<<"["<<i1<<", "<<j1<<"] -> ["<<i2<<", "<<j2<<"]"<<ln;
					// }

					if(flag) mins(ans, (i2-i1+1) * (j2-j1+1));
				}
			}
		}
	}

	cout<<ans<<ln;

	return 0;
}

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