Submission #337158

#	Time	Username	Problem	Language	Result	Execution time	Memory
337158		deadeye	Bitaro the Brave (JOI19_ho_t1)	C++14	100 / 100	446 ms	229740 KiB

joi2019_ho_t1

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define si second
#define ll long long 
typedef pair<int,int> pi;

#ifdef LOCAL
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 69
#endif
template <typename Arg>
void __f(string name, Arg arg) {
	cerr << name << " = " << arg << endl;
}
template <typename Head, typename... Tail>
void __f(string names, Head head, Tail... tail) {
	string cur = "";
	for (auto ch: names){if(ch==','){break;}else{cur+=ch;}}
	string nxt = names.substr(cur.size()+2);
	cerr << cur << " = " << head << ", ";
	__f(nxt, tail...);
}

const int mxn = 3005;
ll H, W, ret;
int row[mxn][mxn][3], col[mxn][mxn][3];
char A[mxn][mxn];
map<char,int> idx;

int rq(int x, int qs, int qe, int idx) {
	return row[x][qe][idx] - row[x][qs - 1][idx];
}

int cq(int x, int qs, int qe, int idx) {
	return col[qe][x][idx] - col[qs - 1][x][idx];
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> H >> W;
	idx['J'] = 0, idx['O'] = 1, idx['I'] = 2;
	for (int i = 1; i <= H; ++i) for (int j = 1; j <= W; ++j) cin >> A[i][j];
	for (int i = 1; i <= H; ++i) {
		for (int j = 1; j <= W; ++j) {
			int n = idx[A[i][j]];
			for (int k = 0; k < 3; ++k) {
				row[i][j][k] = row[i][j - 1][k];
				col[i][j][k] = col[i - 1][j][k];
			}
			++row[i][j][n];
			++col[i][j][n];
		}
	}
	for (int i = 1; i <= H; ++i) {
		for (int j = 1; j <= W; ++j) {
			if (A[i][j] == 'J') {
				ret += rq(i, j + 1, W, 1) * cq(j, i + 1, H, 2);
			}
		}
	}
	cout << ret;
	return 0;
}

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