Submission #785856

#	Time	Username	Problem	Language	Result	Execution time	Memory
785856		flappybird	Raspad (COI17_raspad)	C++17	100 / 100	320 ms	210008 KiB

raspad

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 103030
#define MAXS 22
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int N, M;
int mp[MAX][60];
ll ans;
int vis[MAX][60];
int ccnt;
int dx[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
int dy[8] = { 1, 0, -1, 1, -1, 1, 0, -1 };
pii range[MAX * 60];
bool chk(int x, int y) {
	return 0 <= x && x <= N + 1 && 0 <= y && y <= M + 1;
}
void dfs(int x, int y, int c) {
	if (!chk(x, y)) return;
	if (mp[x][y]) return;
	if (vis[x][y]) return;
	vis[x][y] = c;
	int k;
	for (k = 0; k < 8; k++) dfs(x + dx[k], y + dy[k], c);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N >> M;
	int i, j;
	string s;
	for (i = 1; i <= N; i++) {
		cin >> s;
		for (j = 1; j <= M; j++) mp[i][j] = s[j - 1] == '1';
	}
	int cnt = 0;
	ll v, e, f;
	v = e = f = 0;
	for (i = 1; i <= N; i++) {
		cnt = 0;
		for (j = 1; j <= M; j++) cnt += mp[i][j];
		v += 1ll * cnt * i * (N + 1 - i);
	}
	for (i = 1; i <= N; i++) {
		cnt = 0;
		for (j = 1; j < M; j++) cnt += mp[i][j] & mp[i][j + 1];
		e += 1ll * cnt * i * (N + 1 - i);
	}
	for (i = 2; i <= N; i++) {
		cnt = 0;
		for (j = 1; j <= M; j++) cnt += mp[i][j] & mp[i - 1][j];
		e += 1ll * cnt * (i - 1) * (N + 1 - i);
	}
	dfs(0, 0, -1);
	for (i = 1; i <= N; i++) for (j = 1; j <= M; j++) if (!mp[i][j] && !vis[i][j]) dfs(i, j, ++ccnt);
	for (i = 1; i <= ccnt; i++) range[i] = pii(N + 100, -1000);
	for (i = 1; i <= N; i++) for (j = 1; j <= M; j++) {
		if (vis[i][j]) {
			int c = vis[i][j];
			range[c].first = min(range[c].first, i);
			range[c].second = max(range[c].second, i);
		}
	}
	for (i = 1; i <= ccnt; i++) f += 1ll * (range[i].first - 1) * (N - range[i].second);
	for (i = 2; i <= N; i++) for (j = 2; j <= M; j++) if (mp[i][j] && mp[i - 1][j] && mp[i][j - 1] && mp[i - 1][j - 1]) f += 1ll * (i - 1) * (N + 1 - i);
	cout << v - e + f << ln;
}

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