oj.uz

Submission #825318

# Submission time Handle Problem Language Result Execution time Memory
825318 2023-08-14T17:40:32 Z NhanBeoo Bitaro the Brave (JOI19_ho_t1) C++17
20 / 100
 7 ms 5952 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 1104 KB Output is correct
12 Correct 1 ms 1108 KB Output is correct
13 Correct 1 ms 980 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 1104 KB Output is correct
12 Correct 1 ms 1108 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 5 ms 5460 KB Output is correct
15 Correct 1 ms 3284 KB Output is correct
16 Correct 3 ms 3284 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 6 ms 5952 KB Output is correct
19 Correct 7 ms 5876 KB Output is correct
20 Incorrect 5 ms 5844 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 1104 KB Output is correct
12 Correct 1 ms 1108 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 5 ms 5460 KB Output is correct
15 Correct 1 ms 3284 KB Output is correct
16 Correct 3 ms 3284 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 6 ms 5952 KB Output is correct
19 Correct 7 ms 5876 KB Output is correct
20 Incorrect 5 ms 5844 KB Output isn't correct
21 Halted 0 ms 0 KB -