Submission #825319

#	Time	Username	Problem	Language	Result	Execution time	Memory
825319		NhanBeoo	Bitaro the Brave (JOI19_ho_t1)	C++17	100 / 100	208 ms	159156 KiB

joi2019_ho_t1

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

#define int ll
#define MAX LLONG_MAX
#define st first
#define nd second
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(), x.end()
typedef long long ll;
typedef pair< int, int > ii;
typedef pair< int, ii > iii;
typedef vector< int > vi;
typedef vector< ii > vii;
typedef vector< iii > viii;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
typedef vector< viii > vviii;

const int N = 3005;
char a[N][N];
ii dp[N][N];

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, m; cin >> n >> m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin >> a[i][j];
		}
	}
	for(int i=1; i<=m; i++){
		if(a[n][i] == 'O') dp[n][i] = {1, 0};
		else if(a[n][i] == 'I') dp[n][i] = {0, 1};
		else dp[n][i] = {0, 0};	
	}
	for(int i=1; i<=n; i++){
		if(a[i][m] == 'O') dp[i][m] = {1, 0};
		else if(a[i][m] == 'I') dp[i][m] = {0, 1};
		else dp[i][m] = {0, 0};
	}
	int ans = 0;
	for(int i=n-1; i>=1; i--){
		for(int j=m-1; j>=1; j--){
			if(a[i][j] == 'J'){
				ans += dp[i+1][j].nd * dp[i][j+1].st;
				dp[i][j] = {dp[i][j+1].st, dp[i+1][j].nd};
				
			}
			else if(a[i][j] == 'O'){
				dp[i][j] = {dp[i][j+1].st + 1, dp[i+1][j].nd};
			}
			else{
				dp[i][j] = {dp[i][j+1].st, dp[i+1][j].nd + 1};
			}
		}
	}
	// for(int i=1; i<=n; i++){
		// for(int j=1; j<=m; j++){
			// cout << "{" << dp[i][j].st << ", " << dp[i][j].nd << "} ";
		// }
		// cout << endl;
	// }
	cout << ans;
} 

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