Submission #1277503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277503		almaz	Bitaro the Brave (JOI19_ho_t1)	C++20	100 / 100	285 ms	151548 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
using namespace std;

#define int long long
// #define endl '\n'
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define arr array

const int MOD = 1e9 + 7,INF = 1e18, N = 2e5 + 5;
/*
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
3
1 3 2
3
1 3 3
3
1 3 4
3
1 4 1
3
1 4 2
3
1 4 3
3
1 4 4
3
2 1 1
3
2 1 2
3
2 1 3
3
2 1 4
3
2 2 1
3
2 2 2
3
2 2 3
3
2 2 4
3
2 3 1
3
2 3 2
3
2 3 3
3
2 3 4
3
2 4 1
3
2 4 2
3
2 4 3
3
2 4 4
*/

void solve(){
	int n , m;
	cin >> n >> m;
	
	vector <string> a(n);
	
	for(int i = 0;i < n;i++){
		cin >> a[i];
	}
	
	vector <vector <int>>  cnti(n , vector <int> (m)) , cnto(n , vector <int> (m));
	
	for(int j = 0;j < m;j++){
		if(a[n - 1][j] == 'I'){
			cnti[n - 1][j] = 1;
		}
		for(int i = n - 2;i >= 0;i--){
			cnti[i][j] = cnti[i + 1][j];
			if(a[i][j] == 'I'){
				cnti[i][j]++;
			} 
		}
	}
	
	for(int i = 0;i < n;i++){
		if(a[i][m - 1] == 'O'){
			cnto[i][m - 1] = 1;
		}
		for(int j = m - 2;j >= 0;j--){
			cnto[i][j] = cnto[i][j + 1];
			if(a[i][j] == 'O'){
				cnto[i][j]++;
			}			
		}
	}
	int ans = 0;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			if(a[i][j] == 'J'){
				ans += cnto[i][j] * cnti[i][j];
			}
		}
	}
	cout<<ans<<endl;
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int ti = 1;
    // cin >> ti;
    while (ti--) {
		solve();
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50