Task: | Tontti |
Sender: | quasisphere |
Submission time: | 2015-09-28 00:58:18 +0300 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 14 |
#2 | ACCEPTED | 33 |
#3 | ACCEPTED | 53 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.06 s | 1 | details |
#2 | ACCEPTED | 0.05 s | 1 | details |
#3 | ACCEPTED | 0.04 s | 1 | details |
#4 | ACCEPTED | 0.05 s | 1 | details |
#5 | ACCEPTED | 0.05 s | 1 | details |
#6 | ACCEPTED | 0.09 s | 2 | details |
#7 | ACCEPTED | 0.08 s | 2 | details |
#8 | ACCEPTED | 0.07 s | 2 | details |
#9 | ACCEPTED | 0.07 s | 2 | details |
#10 | ACCEPTED | 0.06 s | 2 | details |
#11 | ACCEPTED | 0.95 s | 3 | details |
#12 | ACCEPTED | 0.98 s | 3 | details |
#13 | ACCEPTED | 0.67 s | 3 | details |
#14 | ACCEPTED | 0.65 s | 3 | details |
#15 | ACCEPTED | 0.65 s | 3 | details |
Code
#include<iostream> #include<vector> #include<map> #include<set> #include<algorithm> #include<cmath> #include<utility> using namespace std; int64_t calc(const vector<vector<int64_t>> &foo, int64_t i, int64_t j, int64_t sqsize) { return foo[i][j] - ((i-sqsize >= 0)?foo[i-sqsize][j]:0) - ((j-sqsize >= 0)?foo[i][j-sqsize]:0) + ((i-sqsize >= 0 && j-sqsize >= 0)?foo[i-sqsize][j-sqsize]:0); } int main(void) { int64_t n,m,x; cin >> n >> m >> x; vector<vector<char>> woods(n,vector<char>(m)); for(int64_t i=0;i<n;i++) { for(int64_t j=0;j<m;j++) { cin >> woods[i][j]; } } vector<vector<int64_t>> foo(n,vector<int64_t>(m,0)); for(int64_t i=0;i<n;i++) { for(int64_t j=0;j<m;j++) { if(woods[i][j] == '*') { foo[i][j]=((j-1>=0)?foo[i][j-1]:0)+((i-1>=0)?foo[i-1][j]:0)-((i-1>=0&&j-1>=0)?foo[i-1][j-1]:0)+1; } else { foo[i][j]=((j-1>=0)?foo[i][j-1]:0)+((i-1>=0)?foo[i-1][j]:0)-((i-1>=0&&j-1>=0)?foo[i-1][j-1]:0); } } } int64_t ways=0; for(int64_t i=0;i<n;i++) { for(int64_t j=0;j<m;j++) { int64_t sqsize=1; for(int64_t blah=2048;blah>=1;blah/=2) { while(sqsize+blah<=min(i+1,j+1) && calc(foo,i,j,sqsize+blah)<=x) sqsize+=blah; } if(calc(foo,i,j,sqsize) != x) continue; int64_t maxsize=sqsize; for(int64_t blah=2048;blah>=1;blah/=2) { while(sqsize-blah>0 && calc(foo,i,j,sqsize-blah)>=x) sqsize-=blah; } int64_t minsize=sqsize; ways+=maxsize-minsize+1; } } cout << ways << '\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: 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 |