Task: | Tontti |
Sender: | Destroy(); |
Submission time: | 2015-10-10 22:59:29 +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.05 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 1 | details |
#3 | ACCEPTED | 0.05 s | 1 | details |
#4 | ACCEPTED | 0.06 s | 1 | details |
#5 | ACCEPTED | 0.05 s | 1 | details |
#6 | ACCEPTED | 0.08 s | 2 | details |
#7 | ACCEPTED | 0.07 s | 2 | details |
#8 | ACCEPTED | 0.07 s | 2 | details |
#9 | ACCEPTED | 0.07 s | 2 | details |
#10 | ACCEPTED | 0.07 s | 2 | details |
#11 | ACCEPTED | 0.90 s | 3 | details |
#12 | ACCEPTED | 0.90 s | 3 | details |
#13 | ACCEPTED | 0.71 s | 3 | details |
#14 | ACCEPTED | 0.76 s | 3 | details |
#15 | ACCEPTED | 0.82 s | 3 | details |
Code
#include <iostream>#include <string>#include <algorithm>using namespace std;int korkeus, leveys, puut;int summataulukko[2000][2000];int vakio;void readInput(int x, int y);int lasku(int i, int j, int korkeus, int leveys, int puut);int summataulukkolaske(int x1, int y1, int x2, int y2);int binarysearch(int maksimi, int x1, int y1, int x2, int y2);int main(){ios_base::sync_with_stdio(0);cin >> korkeus >> leveys >> puut;readInput(leveys, korkeus);int lkm = 0;for (int j = 0; j < korkeus; j++){for (int i = 0; i < leveys; i++){lkm = lkm + lasku(i, j, korkeus, leveys, puut);}}cout << lkm;cin.get();cin.get();}void readInput(int x, int y){for (int j = 0; j < y; j++){for (int i = 0; i < x; i++){char a;cin >> a;vakio = 0;if (a == '*'){vakio = 1;}if (i == 0 && j == 0){summataulukko[i][j] = vakio;}else if (i == 0){summataulukko[i][j] = summataulukko[i][j - 1] + vakio;}else if (j == 0){summataulukko[i][j] = summataulukko[i - 1][j] + vakio;}else{summataulukko[i][j] = summataulukko[i - 1][j] + summataulukko[i][j - 1] + vakio - summataulukko[i - 1][j - 1];}}}}int lasku(int i, int j, int korkeus, int leveys, int puut){int maksimi = min(korkeus - j, leveys - i);int pituus = 0;//int nykyisetpuut = 0;//int lasku = 0;int maxhyppy = 0;int minhyppy = 0;bool maxfound = false;for (int b = maksimi / 2; b >= 1; b /= 2){while (pituus + b < maksimi && summataulukkolaske(i + pituus + b, j + pituus + b, i, j) <= puut) pituus += b;}if (summataulukkolaske(i + pituus, j + pituus, i, j) == puut){maxhyppy = pituus;maxfound = true;}//cout << pituus << '\n';for (int b = maksimi / 2; b >= 1; b /= 2){while (pituus - b >= 0 && summataulukkolaske(i+pituus-b, j+pituus-b, i, j) >= puut) pituus -= b;}if (summataulukkolaske(i + pituus, j + pituus, i, j) == puut){minhyppy = pituus;}//cout << pituus << '\n';/*while (nykyisetpuut <= puut && pituus < maksimi){int lkm2 = summataulukkolaske(i + pituus, j + pituus, i, j);if (lkm2 == puut)lasku += 1;nykyisetpuut = lkm2;pituus++;}int x1 = binarysearch(maksimi, i, j, i, j);int y1 = x1;int max = x1;while (summataulukkolaske(x1 + 1, y1 + 1, i, j) == puut){x1 += 1;y1 += 1;max += 1;}int min = x1;while (summataulukkolaske(x1 - 1, y1 - 1, i, j) == puut){x1 -= 1;y1 -= 1;min -= 1;}*/if (maxfound)return maxhyppy - minhyppy + 1;elsereturn 0;}int summataulukkolaske(int x1, int y1, int x2, int y2){int i = x2 - 1;int j = y2 - 1;int vastaus = 0;if (i < 0 && j < 0){vastaus = summataulukko[x1][y1];}else if (i < 0){vastaus = summataulukko[x1][y1] - summataulukko[x1][j];}else if (j < 0){vastaus = summataulukko[x1][y1] - summataulukko[i][y1];}else{vastaus = summataulukko[x1][y1] - summataulukko[i][y1] - summataulukko[x1][j] + summataulukko[i][j];}return vastaus;}/*int binarysearch(int maksimi, int x1, int y1, int x2, int y2){int laskutulos = summataulukkolaske(x1, y1, x2, y2);if (laskutulos == puut){return x1, y1;}else{if (laskutulos < puut){x1 = x2 + int((maksimi - x1) / 2);y1 = y2 + int((maksimi - x1) / 2);}if (laskutulos > puut){x1 = x2 - int((maksimi - int(x1 / 2)) / 2);y1 = y2 - int((maksimi - int(y1 / 2)) / 2);}binarysearch(maksimi, x1, y1, x2, y2);}}*/
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 |