oj.uz

Submission #165555

# Submission time Handle Problem Language Result Execution time Memory
165555 2019-11-27T12:40:15 Z Sensei Strah (COCI18_strah) C++17
0 / 110
 542 ms 255756 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e3;

char a[MAXN + 7][MAXN + 7];

long long n[MAXN + 7][MAXN + 7];
long long ne[MAXN + 7][MAXN + 7];
long long e[MAXN + 7][MAXN + 7];
long long se[MAXN + 7][MAXN + 7];
long long s[MAXN + 7][MAXN + 7];
long long sw[MAXN + 7][MAXN + 7];
long long w[MAXN + 7][MAXN + 7];
long long nw[MAXN + 7][MAXN + 7];

// int mat[MAXN + 7][MAXN + 7];

#define dbg(x) cerr<<#x<<" : "<<x<<" "

int main () {
	int N, M;

	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++) {
		scanf("\n");
		for (int j = 1; j <= M; j++) {
			scanf("%c", &a[i][j]);
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (a[i][j] != '.') {
				continue;
			}

			if (a[i - 1][j] == '.') {
				n[i][j] = 1 + n[i - 1][j];
			}
			else {
				n[i][j] = 1;
			}

			if (a[i][j - 1] == '.') {
				w[i][j] = 1 + w[i][j - 1];
			}
			else {
				w[i][j] = 1;
			}
		}

		for (int j = M; j >= 1; j--) {
			if (a[i][j] != '.') {
				continue;
			}

			if (a[i][j + 1] == '.') {
				e[i][j] = 1 + e[i][j + 1];
			}
			else {
				e[i][j] = 1;
			}
		}
	}

	for (int i = N; i >= 1; i--) {
		for (int j = 1; j <= M; j++) {
			if (a[i][j] != '.') {
				continue;
			}

			if (a[i + 1][j] == '.') {
				s[i][j] = 1 + s[i + 1][j];
			}
			else {
				s[i][j] = 1;
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (a[i][j] == '.') {
				nw[i][j] = 1 + max(0LL, nw[i - 1][j] + nw[i][j - 1] - nw[i - 1][j - 1]);
			}
		}

		for (int j = M; j >= 1; j--) {
			if (a[i][j] == '.') {
				ne[i][j] = 1 + max(0LL, ne[i - 1][j] + ne[i][j + 1] - ne[i - 1][j + 1]);
			}
		}
	}

	for (int i = N; i >= 1; i--) {
		for (int j = 1; j <= M; j++) {
			if (a[i][j] == '.') {
				sw[i][j] = 1 + max(0LL, sw[i + 1][j] + sw[i][j - 1] - sw[i + 1][j - 1]);
			}
		}

		for (int j = M; j >= 1; j--) {
			if (a[i][j] == '.') {
				se[i][j] = 1 + max(0LL, se[i + 1][j] + se[i][j + 1] - se[i + 1][j + 1]);
			}
		}
	}

	long long ans = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (a[i][j] != '.') {
				continue;
			}

			// dbg(i);dbg(j);

			// mat[i][j] = mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1] + n[i][j] + w[i][j] - 1;

			// dbg(mat[i][j]);
			// cerr << "\n";

			// ans += mat[i][j];

			// dbg(i);dbg(j);
			// cerr << "\n";
			// dbg(n[i][j]);dbg(e[i][j]);dbg(s[i][j]);dbg(w[i][j]);
			// cerr << "\n";
			// dbg(ne[i][j]);dbg(se[i][j]);dbg(sw[i][j]);dbg(nw[i][j]);
			// cerr << "\n";

			ans += nw[i][j] * ne[i][j] * se[i][j] * sw[i][j]
					/ (
					n[i][j] * e[i][j] * s[i][j] * w[i][j]
					)
					// + 1;
					;
		}
	}

	cout << ans << "\n";

	return 0;
}

Compilation message

strah.cpp: In function 'int main()':
strah.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
strah.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n");
   ~~~~~^~~~~~
strah.cpp:30:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%c", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 16248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 16348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16248 KB Output is correct
2 Incorrect 24 ms 16376 KB Output isn't correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 94356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 362 ms 170400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 223 ms 109384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 79040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 542 ms 255756 KB Output isn't correct
2 Halted 0 ms 0 KB -