Task: | Tontti |
Sender: | Kuha |
Submission time: | 2015-09-29 17:41:10 +0300 |
Language: | C++ |
Status: | READY |
Result: | 86 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | ACCEPTED | 33 |
#3 | ACCEPTED | 53 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.05 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 1 | details |
#3 | ACCEPTED | 0.06 s | 1 | details |
#4 | ACCEPTED | 0.06 s | 1 | details |
#5 | ACCEPTED | 0.06 s | 1 | details |
#6 | ACCEPTED | 0.08 s | 2 | details |
#7 | ACCEPTED | 0.08 s | 2 | details |
#8 | ACCEPTED | 0.09 s | 2 | details |
#9 | ACCEPTED | 0.07 s | 2 | details |
#10 | ACCEPTED | 0.07 s | 2 | details |
#11 | ACCEPTED | 0.86 s | 3 | details |
#12 | ACCEPTED | 0.86 s | 3 | details |
#13 | ACCEPTED | 0.58 s | 3 | details |
#14 | ACCEPTED | 0.63 s | 3 | details |
#15 | ACCEPTED | 0.65 s | 3 | details |
Code
#include <iostream>#include <algorithm>#include <queue>#include <stack>#include <string>#define INF 999999999#define ll long longusing namespace std;int main(){int n, m, tr;cin>>n>>m>>tr;char c[n][m];int v[n][m][2];for (int y = 0; y < n; y++) {for (int x = 0; x < m; x++) {cin>>c[y][x];v[y][x][0] = 0;if (x > 0) v[y][x][0] = v[y][x - 1][0];if (c[y][x] == '*') v[y][x][0]++;v[y][x][1] = v[y][x][0];if (y > 0) v[y][x][1] += v[y - 1][x][1];}}int ans = 0;for (int y = 0; y < n; y++) {for (int x = 0; x < m; x++) {int i = 0;int mi = -1;int mx = -1;int mini = min(m - x, n - y); // BIN��RIHAKU!bool tf = false;i = 0;for (int t = mini / 2; t >= 0; t /= 2) {bool b = true;while (b && i + t < mini) {i += t;b = true;int w = v[y+i][x+i][1];if (x > 0 && y > 0) w += v[y-1][x-1][1];if (x > 0) w -= v[y+i][x-1][1];if (y > 0) w -= v[y-1][x+i][1];if (w > tr) b = false;else if (w == tr) {b = false;tf = true;}//if (b) cout<<w<<" "<<i<<" too big!"<<endl;//else cout<<w<<" "<<i<<" secondary!"<<endl;if (b) mi = i;else i -= t;if (t == 0) break;}if (t == 0) break;}if (!tf) continue;i = 0;for (int t = mini / 2; t >= 1; t /= 2) {bool b = true;while (b && i + t < mini) {i += t;b = true;int w = v[y+i][x+i][1];if (x > 0 && y > 0) w += v[y-1][x-1][1];if (x > 0) w -= v[y+i][x-1][1];if (y > 0) w -= v[y-1][x+i][1];if (w > tr) b = false;if (b) mx = i;else i -= t;}}//cout<<x<<" "<<y<<" "<<mi<<" "<<mx<<endl;if (tf) ans += mx - mi;}}cout<<ans<<endl;return 0;}
Test details
Test 1
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 10 1 ......*... .......*.. *..*....*. *....*.... ... |
correct output |
---|
94 |
user output |
---|
90 |
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: ACCEPTED
input |
---|
500 500 1 ................................. |
correct output |
---|
9552040 |
user output |
---|
9552040 |
Test 7
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 5 ................................. |
correct output |
---|
1536063 |
user output |
---|
1536063 |
Test 8
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 25000 **...*...**..*.*..*.**.*..*.*.... |
correct output |
---|
288 |
user output |
---|
288 |
Test 9
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 12500 **.**.*..*...*.**...*.***........ |
correct output |
---|
786 |
user output |
---|
786 |
Test 10
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 5000 .*.*.**..*.*.**.**..*..**...*.... |
correct output |
---|
1763 |
user output |
---|
1763 |
Test 11
Group: 3
Verdict: ACCEPTED
input |
---|
2000 2000 1 ................................. |
correct output |
---|
489611392 |
user output |
---|
489611392 |
Test 12
Group: 3
Verdict: ACCEPTED
input |
---|
2000 2000 5 ................................. |
correct output |
---|
120725884 |
user output |
---|
120725884 |
Test 13
Group: 3
Verdict: ACCEPTED
input |
---|
2000 2000 400000 ..*..**.**.**.*.***...**.*..**... |
correct output |
---|
1849 |
user output |
---|
1849 |
Test 14
Group: 3
Verdict: ACCEPTED
input |
---|
2000 2000 200000 ***.*....*.*..*....**..*..*.*.... |
correct output |
---|
2665 |
user output |
---|
2665 |
Test 15
Group: 3
Verdict: ACCEPTED
input |
---|
2000 2000 80000 **.**...*.***.**....**.*....*.... |
correct output |
---|
5587 |
user output |
---|
5587 |