#include "bits/stdc++.h"
using namespace std;
const int MAXN = 3005;
char board[MAXN][MAXN];
long long pref_orb[MAXN][MAXN];
long long pref_ingot[MAXN][MAXN];
// Sol O(h * w) Prefix sum. let's store the prefix sum of orb for every row and ingot for every column. After that let's iterate through our jewels. Let's think we are at a jewel with position (i, j). So to calculate our magic spell which has this jewel, we should multiply possible orb count and ingot count. Since these two are independent from each other (they only depend jewel's position), we can just multiply it. Our orb count is pref_orb[i][w] - pref_orb[i][j] and ingot count is pref_ingot[h][j] - pref_ingot[i][j]. We will multiply these two and add it to our answer.
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int h, w;
cin >> h >> w;
for(int i = 1; i <= h; i++)
{
pref_orb[i][0] = 0;
for(int a = 1; a <= w; a++) {
cin >> board[i][a];
pref_orb[i][a] = pref_orb[i][a-1] + (board[i][a] == 'O' ? 1 : 0);
}
}
for(int col = 1; col <= w; col++)
{
for(int row = 1; row <= h; row++)
{
pref_ingot[row][col] = pref_ingot[row-1][col] + (board[row][col] == 'I' ? 1 : 0);
}
}
long long ans = 0;
for(int row = 1; row <= h; row++)
{
for(int col = 1; col <= w; col++)
{
if(board[row][col] == 'J')
{
ans += (pref_orb[row][w] - pref_orb[row][col]) * (pref_ingot[h][col] - pref_ingot[row][col]);
}
//cout << row << " " << col << " " << ans << "\n";
}
}
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 14 |
Correct |
7 ms |
8812 KB |
Output is correct |
| 15 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 16 |
Correct |
4 ms |
5128 KB |
Output is correct |
| 17 |
Correct |
1 ms |
468 KB |
Output is correct |
| 18 |
Correct |
9 ms |
9684 KB |
Output is correct |
| 19 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 20 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 21 |
Correct |
8 ms |
9684 KB |
Output is correct |
| 22 |
Correct |
7 ms |
9556 KB |
Output is correct |
| 23 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 24 |
Correct |
9 ms |
9684 KB |
Output is correct |
| 25 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 26 |
Correct |
8 ms |
9556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 14 |
Correct |
7 ms |
8812 KB |
Output is correct |
| 15 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 16 |
Correct |
4 ms |
5128 KB |
Output is correct |
| 17 |
Correct |
1 ms |
468 KB |
Output is correct |
| 18 |
Correct |
9 ms |
9684 KB |
Output is correct |
| 19 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 20 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 21 |
Correct |
8 ms |
9684 KB |
Output is correct |
| 22 |
Correct |
7 ms |
9556 KB |
Output is correct |
| 23 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 24 |
Correct |
9 ms |
9684 KB |
Output is correct |
| 25 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 26 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 27 |
Correct |
295 ms |
150156 KB |
Output is correct |
| 28 |
Correct |
12 ms |
26324 KB |
Output is correct |
| 29 |
Correct |
15 ms |
13220 KB |
Output is correct |
| 30 |
Correct |
1 ms |
724 KB |
Output is correct |
| 31 |
Correct |
229 ms |
125160 KB |
Output is correct |
| 32 |
Correct |
288 ms |
150272 KB |
Output is correct |
| 33 |
Correct |
296 ms |
149780 KB |
Output is correct |
| 34 |
Correct |
268 ms |
145228 KB |
Output is correct |
| 35 |
Correct |
288 ms |
150208 KB |
Output is correct |
| 36 |
Correct |
299 ms |
149748 KB |
Output is correct |
| 37 |
Correct |
325 ms |
150276 KB |
Output is correct |
| 38 |
Correct |
204 ms |
124684 KB |
Output is correct |
| 39 |
Correct |
205 ms |
124724 KB |
Output is correct |
