#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 |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1492 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 |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1492 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 |
8788 KB |
Output is correct |
| 15 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 16 |
Correct |
6 ms |
5204 KB |
Output is correct |
| 17 |
Correct |
0 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 |
8 ms |
9556 KB |
Output is correct |
| 23 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 24 |
Correct |
8 ms |
9684 KB |
Output is correct |
| 25 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 26 |
Correct |
8 ms |
9496 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 |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1492 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 |
8788 KB |
Output is correct |
| 15 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 16 |
Correct |
6 ms |
5204 KB |
Output is correct |
| 17 |
Correct |
0 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 |
8 ms |
9556 KB |
Output is correct |
| 23 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 24 |
Correct |
8 ms |
9684 KB |
Output is correct |
| 25 |
Correct |
8 ms |
9556 KB |
Output is correct |
| 26 |
Correct |
8 ms |
9496 KB |
Output is correct |
| 27 |
Correct |
297 ms |
150176 KB |
Output is correct |
| 28 |
Correct |
11 ms |
26332 KB |
Output is correct |
| 29 |
Correct |
15 ms |
13244 KB |
Output is correct |
| 30 |
Correct |
1 ms |
724 KB |
Output is correct |
| 31 |
Correct |
227 ms |
125196 KB |
Output is correct |
| 32 |
Correct |
288 ms |
150348 KB |
Output is correct |
| 33 |
Correct |
304 ms |
149716 KB |
Output is correct |
| 34 |
Correct |
262 ms |
145296 KB |
Output is correct |
| 35 |
Correct |
293 ms |
150540 KB |
Output is correct |
| 36 |
Correct |
287 ms |
149708 KB |
Output is correct |
| 37 |
Correct |
321 ms |
150268 KB |
Output is correct |
| 38 |
Correct |
207 ms |
124768 KB |
Output is correct |
| 39 |
Correct |
207 ms |
124716 KB |
Output is correct |
