Submission #1191735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191735		Tob	Raspad (COI17_raspad)	C++20	100 / 100	362 ms	75592 KiB

raspad

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e5 + 7, M = 51;

int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};

ll n, m;
int mnx, mxx, mny, mxy;
int mat[N][M], bio[N][M];

void dfs(int x, int y) {
	bio[x][y] = 1;
	mnx = min(mnx, x);
	mny = min(mny, y);
	mxx = max(mxx, x);
	mxy = max(mxy, y);
	for (int i = 0; i < 8; i++) {
		int nx = x+dx[i], ny = y+dy[i];
		if (nx >= 0 && nx < n && ny >= 0 && ny < m && !bio[nx][ny] && !mat[nx][ny]) dfs(nx, ny);
	}
}

int main () {
	FIO;
	cin >> n >> m;
	ll res = -n*(n+1)/2;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char cc; cin >> cc;
			mat[i][j] = cc-'0';
			if (!mat[i][j]) res += (ll)(i+1)*(n-i);
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < m; j++) res -= (!mat[i][j] || !mat[i][j-1])*(ll)(i+1)*(n-i);
	}
	
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < m; j++) res -= (!mat[i][j] || !mat[i-1][j])*(ll)i*(n-i);
	}
	
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			res += (!mat[i][j] || !mat[i-1][j] || !mat[i][j-1] || !mat[i-1][j-1])*(ll)i*(n-i);
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!mat[i][j] && !bio[i][j]) {
				mnx = mxx = i;
				mny = mxy = j;
				dfs(i, j);
				if (mny > 0 && mxy < m-1) res -= (ll)mnx*(n-mxx-1);
			}
		}
	}
	
	cout << -res << "\n";

	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39