Submission #965222

#	Time	Username	Problem	Language	Result	Execution time	Memory
965222		pcc	Garden (JOI23_garden)	C++17	30 / 100	106 ms	9788 KiB

garden

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 320;

int arr[mxn][mxn];
vector<pii> t1,t2;
int N,M,D;

void add(int r1,int c1,int r2,int c2,int v = 1){
	if(r1>r2||c1>c2)return;
	r1 = max(0,r1),c1 = max(0,c1),r2 = max(0,r2),c2 = max(0,c2);
	arr[r1][c1]+=v;arr[r1][c2+1]-=v;
	arr[r2+1][c1]-=v;arr[r2+1][c2+1]+=v;
	return;
}

bool check(int r,int c){
	memset(arr,0,sizeof(arr));
	for(auto &i:t1){
		add(i.fs-r+1,i.sc-c+1,i.fs,i.sc);
		add(i.fs+D-r+1,i.sc-c+1,i.fs+D,i.sc);
		add(i.fs-r+1,i.sc+D-c+1,i.fs,i.sc+D);
		add(i.fs+D-r+1,i.sc+D-c+1,i.fs+D,i.sc+D);
	}
	for(auto &i:t2){
		add(0,i.sc-c+1,D*2,i.sc);
		add(0,i.sc+D-c+1,D*2,i.sc+D);
		add(i.fs-r+1,0,i.fs,D*2);
		add(i.fs+D-r+1,0,i.fs+D,D*2);
		add(i.fs-r+1,i.sc-c+1,i.fs,i.sc,-1);
		add(i.fs+D-r+1,i.sc-c+1,i.fs+D,i.sc,-1);
		add(i.fs-r+1,i.sc+D-c+1,i.fs,i.sc+D,-1);
		add(i.fs+D-r+1,i.sc+D-c+1,i.fs+D,i.sc+D,-1);
	}
	for(int i = 0;i<mxn;i++){
		for(int j = 0;j<mxn;j++){
			if(i)arr[i][j] += arr[i-1][j];
			if(j)arr[i][j] += arr[i][j-1];
			if(i&&j)arr[i][j] -= arr[i-1][j-1];
		}
	}
	/*
	cout<<r<<' '<<c<<":"<<endl;
	for(int i = 0;i<D*3;i++){
		for(int j = 0;j<D*3;j++)cout<<arr[i][j]<<' ';cout<<endl;
	}

   */
	for(int i = 0;i<mxn;i++){
		for(int j = 0;j<mxn;j++){
			if(arr[i][j] == N+M)return true;
		}
	}
	return false;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>D;
	for(int i = 0;i<N;i++){
		pii p;
		cin>>p.fs>>p.sc;
		p.fs += D,p.sc += D;
		t1.push_back(p);
	}
	for(int i = 0;i<M;i++){
		pii p;
		cin>>p.fs>>p.sc;
		p.fs += D,p.sc += D;
		t2.push_back(p);
	}
	int pt = 1;
	int ans = 1e9;
	for(int i = D;i>=1;i--){
		while(pt<=D&&!check(i,pt))pt++;
		if(pt<=D)ans = min(ans,pt*i);
	}
	cout<<ans;
}

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