oj.uz

Submission #785856

# Submission time Handle Problem Language Result Execution time Memory
785856 2023-07-17T16:37:30 Z flappybird Raspad (COI17_raspad) C++17
100 / 100
 320 ms 210008 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 3 ms 1748 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 980 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 30088 KB Output is correct
2 Correct 150 ms 112684 KB Output is correct
3 Correct 105 ms 64528 KB Output is correct
4 Correct 90 ms 93232 KB Output is correct
5 Correct 42 ms 31716 KB Output is correct
6 Correct 130 ms 87624 KB Output is correct
7 Correct 83 ms 61772 KB Output is correct
8 Correct 79 ms 58844 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 3 ms 1748 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 24 ms 30088 KB Output is correct
15 Correct 150 ms 112684 KB Output is correct
16 Correct 105 ms 64528 KB Output is correct
17 Correct 90 ms 93232 KB Output is correct
18 Correct 42 ms 31716 KB Output is correct
19 Correct 130 ms 87624 KB Output is correct
20 Correct 83 ms 61772 KB Output is correct
21 Correct 79 ms 58844 KB Output is correct
22 Correct 224 ms 125612 KB Output is correct
23 Correct 213 ms 65288 KB Output is correct
24 Correct 161 ms 66028 KB Output is correct
25 Correct 313 ms 210008 KB Output is correct
26 Correct 215 ms 74188 KB Output is correct
27 Correct 248 ms 135088 KB Output is correct
28 Correct 200 ms 67256 KB Output is correct
29 Correct 320 ms 164444 KB Output is correct
30 Correct 209 ms 74304 KB Output is correct
31 Correct 202 ms 68044 KB Output is correct
32 Correct 164 ms 73644 KB Output is correct
33 Correct 168 ms 77876 KB Output is correct
34 Correct 215 ms 93624 KB Output is correct