Submission #1258814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258814		hello10	Bitaro the Brave (JOI19_ho_t1)	C++20	100 / 100	803 ms	91892 KiB

joi2019_ho_t1

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define MAXN 3005
#define inf 1e15
using namespace std;
int n, m, res=0;
char a[MAXN][MAXN];
vector<int> mpo[MAXN], mpi[MAXN];
signed main(){
	cin>>n>>m;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			cin>>a[i][j];
			if (a[i][j]=='O'){
				mpo[i].push_back(j);
			}
			else if (a[i][j]=='I'){
				mpi[j].push_back(i);
			}
		}
	}
	for (int i=1; i<=n; i++){
		sort (mpo[i].begin(), mpo[i].end());
	}
	for (int i=1; i<=m; i++){
		sort (mpi[i].begin(), mpi[i].end());
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			if (a[i][j]=='J'){
				int x=upper_bound(mpo[i].begin(), mpo[i].end(), j)-mpo[i].begin();
				int y=upper_bound(mpi[j].begin(), mpi[j].end(), i)-mpi[j].begin();
//				cout<<i<<" "<<j<<" "<<x<<" "<<y<<endl;
//
//				for (auto x:mpo[i]){
//					cout<<x<<" ";
//				}
//				cout<<endl;
                x=(int)mpo[i].size()-x;
                y=(int)mpi[j].size()-y;
				res+=x*y;
			}
		}
	}
	cout<<res;
}

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