oj.uz

Submission #785855

# Submission time Handle Problem Language Result Execution time Memory
785855 2023-07-17T16:36:56 Z flappybird Raspad (COI17_raspad) C++17
61 / 100
 221 ms 127436 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];
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 328 KB Output is correct
4 Correct 1 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 328 KB Output is correct
4 Correct 1 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 4 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 2 ms 980 KB Output is correct
11 Correct 3 ms 1848 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 1108 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30788 KB Output is correct
2 Correct 154 ms 114120 KB Output is correct
3 Correct 108 ms 66096 KB Output is correct
4 Correct 112 ms 94704 KB Output is correct
5 Correct 41 ms 32204 KB Output is correct
6 Correct 126 ms 89164 KB Output is correct
7 Correct 82 ms 63296 KB Output is correct
8 Correct 79 ms 60160 KB Output is correct

Subtask #4
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 328 KB Output is correct
4 Correct 1 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 4 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 2 ms 980 KB Output is correct
11 Correct 3 ms 1848 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 2 ms 1108 KB Output is correct
14 Correct 21 ms 30788 KB Output is correct
15 Correct 154 ms 114120 KB Output is correct
16 Correct 108 ms 66096 KB Output is correct
17 Correct 112 ms 94704 KB Output is correct
18 Correct 41 ms 32204 KB Output is correct
19 Correct 126 ms 89164 KB Output is correct
20 Correct 82 ms 63296 KB Output is correct
21 Correct 79 ms 60160 KB Output is correct
22 Correct 221 ms 127436 KB Output is correct
23 Incorrect 217 ms 66948 KB Output isn't correct
24 Halted 0 ms 0 KB -