Task: | Tontti |
Sender: | 6502 |
Submission time: | 2015-09-29 19:11:14 +0300 |
Language: | C++ |
Status: | READY |
Result: | 14 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 14 |
#2 | TIME LIMIT EXCEEDED | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.05 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 1 | details |
#3 | ACCEPTED | 0.05 s | 1 | details |
#4 | ACCEPTED | 0.05 s | 1 | details |
#5 | ACCEPTED | 0.05 s | 1 | details |
#6 | TIME LIMIT EXCEEDED | -- | 2 | details |
#7 | TIME LIMIT EXCEEDED | -- | 2 | details |
#8 | TIME LIMIT EXCEEDED | -- | 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | TIME LIMIT EXCEEDED | -- | 2 | details |
#11 | TIME LIMIT EXCEEDED | -- | 3 | details |
#12 | TIME LIMIT EXCEEDED | -- | 3 | details |
#13 | TIME LIMIT EXCEEDED | -- | 3 | details |
#14 | TIME LIMIT EXCEEDED | -- | 3 | details |
#15 | TIME LIMIT EXCEEDED | -- | 3 | details |
Code
#include <iostream> #include <math.h> #include <stdio.h> using namespace std; int main() { cin.sync_with_stdio(false); int i, j, n, m, k, x, q, w, o, p; int sz, s; cin >> n >> m >> k; char input[n][m]; int a[n*m]; int f[n*m]; for (i = 0; i < n; i++) cin >> input[i]; sz = (int)ceil(sqrt((double)k)); x = 0; for (i = 0; i < n; i++) for (j = 0; j < m; j++) { a[i*m+j] = !(input[i][j]=='.'); f[i*m+j] = 0; if(k<2) x += a[i*m+j]^k^1; } int c = max(sz,2); int g = 0, h = 0, d, z, first = 1, scale = 1; for (s = c; s <= min(n,m); s++) { z = s - 1; first = 1; for (i = z; i < n; i++) { if (i > 0 && i < n) { q = i * m; w = q - s * m; for (o = 0; o < s; o++, q++, w++) h += (a[q] - a[w]); g = h; } scale = 0; for (j = z; j < m; j++) { d = i*m+j; int t = f[d]; if (first) { first = 0; if (s == c) { for (q = 0; q < s; q++) { for (w = 0; w < s; w++) { t += a[q*m+w]; } } g = h = t; } else { int iz = (i-z)*m, jz = j-z, iq = i * m, jq = j; for (q = 0; q < z; q++) { t += a[iz+jq]; t += a[iq+jz]; iq-=m;jq--; } g = h = t+a[iz+jz]; } scale = 1; } else if (scale) { q = j; w = q - s; p = (i-z)*m; for (o = 0; o < s; o++, p+=m) { g += (a[p+q] - a[p+w]); } } else scale = 1; f[d] = t = g; x += (t == k); } } } cout << x << "\n"; return 0; }
Test details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 1 ......*... .......*.. *..*....*. *....*.... ... |
correct output |
---|
94 |
user output |
---|
94 |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 5 ********** ********** ********** ********** ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 10 **...*...* *..*.**.*. ...**.*..* *...**.*.. ... |
correct output |
---|
4 |
user output |
---|
4 |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 5 ****...... *.*.**..** ....*.*..* ...*.***.. ... |
correct output |
---|
16 |
user output |
---|
16 |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
10 10 2 **.***..*. ...*.*.... .***.*...* ***.***..* ... |
correct output |
---|
30 |
user output |
---|
30 |
Test 6
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 1 ................................. |
correct output |
---|
9552040 |
user output |
---|
(empty) |
Test 7
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 5 ................................. |
correct output |
---|
1536063 |
user output |
---|
(empty) |
Test 8
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 25000 **...*...**..*.*..*.**.*..*.*.... |
correct output |
---|
288 |
user output |
---|
(empty) |
Test 9
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 12500 **.**.*..*...*.**...*.***........ |
correct output |
---|
786 |
user output |
---|
(empty) |
Test 10
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 5000 .*.*.**..*.*.**.**..*..**...*.... |
correct output |
---|
1763 |
user output |
---|
(empty) |
Test 11
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 1 ................................. |
correct output |
---|
489611392 |
user output |
---|
(empty) |
Test 12
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 5 ................................. |
correct output |
---|
120725884 |
user output |
---|
(empty) |
Test 13
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 400000 ..*..**.**.**.*.***...**.*..**... |
correct output |
---|
1849 |
user output |
---|
(empty) |
Test 14
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 200000 ***.*....*.*..*....**..*..*.*.... |
correct output |
---|
2665 |
user output |
---|
(empty) |
Test 15
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
2000 2000 80000 **.**...*.***.**....**.*....*.... |
correct output |
---|
5587 |
user output |
---|
(empty) |