#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
const int N = 3000 + 5;
const int mod = 1e9 + 7;
void print(){cerr << '\n';} template<typename T1, typename ...T2>
void print(const T1 &a, const T2 &...b){cerr << a << ' ', print(b...);}
int m, n;
char a[N][N];
int cnt[N][N], cnt2[N][N];
void sub3()
{
ll res = 0;
for(int i = m; i >= 1; i--)
for(int j = 1; j <= n; j++)
cnt[i][j] = cnt[i + 1][j] + (a[i][j] == 'I');
for(int i = 1; i <= m; i++)
for(int j = n; j >= 1; j--)
cnt2[i][j] = cnt2[i][j + 1] + (a[i][j] == 'O');
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++) if(a[i][j] == 'J')
res += 1ll * cnt[i + 1][j] * cnt2[i][j + 1];
cout << res;
}
void sub2()
{
ll res = 0;
for(int i = m; i >= 1; i--)
for(int j = 1; j <= n; j++)
cnt[i][j] = cnt[i + 1][j] + (a[i][j] == 'I');
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++) if(a[i][j] == 'J')
for(int l = j + 1; l <= n; l++) if(a[i][l] == 'O')
res += cnt[i + 1][j];
cout << res;
}
void sub1()
{
ll res = 0;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++) if(a[i][j] == 'J')
for(int l = j + 1; l <= n; l++) if(a[i][l] == 'O')
for(int k = i + 1; k <= m; k++) if(a[k][j] == 'I')
res++;
cout << res;
}
void solve()
{
cin >> m >> n;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
cin >> a[i][j];
if(m <= 100 && n <= 100)
sub1();
else if(m <= 500 && n <= 500)
sub2();
else
sub3();
}
signed main()
{
// #ifndef ONLINE_JUDGE
// freopen("gap.inp", "r", stdin);
// freopen("gap.out", "w", stdout);
// cin.tie(0) -> sync_with_stdio(0);
// #endif
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
312 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
4 ms |
576 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
9 ms |
588 KB |
Output is correct |
8 |
Correct |
4 ms |
596 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
8 ms |
468 KB |
Output is correct |
11 |
Correct |
5 ms |
596 KB |
Output is correct |
12 |
Correct |
2 ms |
596 KB |
Output is correct |
13 |
Correct |
8 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
312 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
4 ms |
576 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
9 ms |
588 KB |
Output is correct |
8 |
Correct |
4 ms |
596 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
8 ms |
468 KB |
Output is correct |
11 |
Correct |
5 ms |
596 KB |
Output is correct |
12 |
Correct |
2 ms |
596 KB |
Output is correct |
13 |
Correct |
8 ms |
596 KB |
Output is correct |
14 |
Correct |
35 ms |
4728 KB |
Output is correct |
15 |
Correct |
2 ms |
3156 KB |
Output is correct |
16 |
Correct |
18 ms |
2772 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
53 ms |
5000 KB |
Output is correct |
19 |
Correct |
20 ms |
4948 KB |
Output is correct |
20 |
Correct |
34 ms |
4896 KB |
Output is correct |
21 |
Correct |
54 ms |
4992 KB |
Output is correct |
22 |
Correct |
35 ms |
4928 KB |
Output is correct |
23 |
Correct |
34 ms |
4908 KB |
Output is correct |
24 |
Correct |
60 ms |
4992 KB |
Output is correct |
25 |
Correct |
20 ms |
5056 KB |
Output is correct |
26 |
Correct |
33 ms |
4896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
312 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
4 ms |
576 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
9 ms |
588 KB |
Output is correct |
8 |
Correct |
4 ms |
596 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
8 ms |
468 KB |
Output is correct |
11 |
Correct |
5 ms |
596 KB |
Output is correct |
12 |
Correct |
2 ms |
596 KB |
Output is correct |
13 |
Correct |
8 ms |
596 KB |
Output is correct |
14 |
Correct |
35 ms |
4728 KB |
Output is correct |
15 |
Correct |
2 ms |
3156 KB |
Output is correct |
16 |
Correct |
18 ms |
2772 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
53 ms |
5000 KB |
Output is correct |
19 |
Correct |
20 ms |
4948 KB |
Output is correct |
20 |
Correct |
34 ms |
4896 KB |
Output is correct |
21 |
Correct |
54 ms |
4992 KB |
Output is correct |
22 |
Correct |
35 ms |
4928 KB |
Output is correct |
23 |
Correct |
34 ms |
4908 KB |
Output is correct |
24 |
Correct |
60 ms |
4992 KB |
Output is correct |
25 |
Correct |
20 ms |
5056 KB |
Output is correct |
26 |
Correct |
33 ms |
4896 KB |
Output is correct |
27 |
Correct |
537 ms |
87984 KB |
Output is correct |
28 |
Correct |
13 ms |
25940 KB |
Output is correct |
29 |
Correct |
39 ms |
7744 KB |
Output is correct |
30 |
Correct |
2 ms |
596 KB |
Output is correct |
31 |
Correct |
388 ms |
72484 KB |
Output is correct |
32 |
Correct |
520 ms |
88416 KB |
Output is correct |
33 |
Correct |
525 ms |
88204 KB |
Output is correct |
34 |
Correct |
450 ms |
84020 KB |
Output is correct |
35 |
Correct |
528 ms |
88508 KB |
Output is correct |
36 |
Correct |
528 ms |
88156 KB |
Output is correct |
37 |
Correct |
557 ms |
88508 KB |
Output is correct |
38 |
Correct |
385 ms |
72520 KB |
Output is correct |
39 |
Correct |
369 ms |
72268 KB |
Output is correct |