The Darkness

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

struct MaxFlow{
	vector<vector<int> > f;
	vector<vector<int> > g;
	vector<int> used;
	int cc;
	int flow(int x, int t, int fl, int miv){
		if (x==t) return fl;
		used[x]=cc;
		for (int nx:g[x]){
			if (used[nx]!=cc&&f[x][nx]>=miv){
				int r=flow(nx, t, min(fl, f[x][nx]), miv);
				if (r>0){
					f[x][nx]-=r;f[nx][x]+=r;
					return r;
				}
			}
		}
		return 0;
	}
	int getMaxFlow(int source, int sink){
		cc=1;
		int r=0;
		while (int t=flow(source, sink, 1e8, 1)){
			r+=t;
			cc++;
		}
		return r;
	}
	void addEdge(int a, int b, int c){
// 		cout<<a<<" "<<b<<" "<<c<<endl;
		if (f[a][b]==0&&f[b][a]==0){
			g[a].push_back(b);
			g[b].push_back(a);
		}
		f[a][b]+=c;
	}
	MaxFlow(int n) : f(n+1), g(n+1), used(n+1) {
		for (int i=1;i<=n;i++){
			f[i]=vector<int>(n+1);
		}
	}
};

ld lil[33][33];
int is[33][33];

int sq(int x){
	return x*x;
}

int cc(int x, int y){
	return x+32*y+1;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ld b;
	cin>>b;
	ld h;
	cin>>h;
	int r,c;
	cin>>r>>c;
	for (int i=0;i<r;i++){
		string s;
		cin>>s;
		for (int ii=0;ii<c;ii++){
			int ls=s[ii]-'0';
			for (int j=0;j<r;j++){
				for (int jj=0;jj<c;jj++){
					lil[j][jj]+=(ld)ls/(ld)(h*h+sq(i-j)+sq(ii-jj));
				}
			}
		}
	}
	for (int i=0;i<r;i++){
		for (int ii=0;ii<c;ii++){
			if (lil[i][ii]<b){
				is[i][ii]=1;
			}
		}
	}
	MaxFlow mf(2022);
	int source=2015;
	int sink=2016;
	for (int i=1;i<r-1;i++){
		for (int ii=1;ii<c-1;ii++){
			if (is[i][ii]) mf.addEdge(source, cc(i, ii), 1e8);
			for (int j=-1;j<=1;j++){
				for (int jj=-1;jj<=1;jj++){
					if ((j==0)^(jj==0)){
						if (is[i][ii]==0&&is[i+j][ii+jj]==0) mf.addEdge(cc(i, ii), cc(i+j, ii+jj), 43);
						else mf.addEdge(cc(i, ii), cc(i+j, ii+jj), 11);
					}
				}
			}
		}
	}
	for (int i=0;i<r;i++){
		for (int ii=0;ii<c;ii++){
			if (i==0||i==r-1||ii==0||ii==c-1){
				mf.addEdge(cc(i, ii), sink, 1e8);
			}
		}
	}
	cout<<mf.getMaxFlow(source, sink)<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED