oj.uz

Submission #1037993

# Submission time Handle Problem Language Result Execution time Memory
1037993 2024-07-29T11:51:57 Z vako_p Dango Maker (JOI18_dango_maker) C++14
0 / 100
 1 ms 2648 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 3e3 + 5;
ll n,dp[mxN][mxN][2],ii,jj,m;
char a[mxN][mxN];

bool check(ll i, ll j, char ch){
	if(i >= n or i < 0 or j >= m or j < 0) return false;
	return (a[i][j] == ch);
}

void f(ll i, ll j){
	while(i >= 0 and j < m){
		ii = i;
		jj = j;
		if(j > 0 and i + 1 < n){
			dp[i][j][0] = dp[i][j][1] = max(dp[i + 1][j - 1][1], dp[i + 1][j - 1][0]);
		}
		if(a[i][j] != 'R'){
			i--;
			j++;
			continue;
		}
		// 0 -- > R
		// 1 -- > D 
		if(check(i + 1, j, 'G') and check(i + 2, j, 'W')){
			if(j > 0 and i + 1 < n) dp[i][j][1] = max(dp[i][j][1], dp[i + 1][j - 1][1] + 1);
			else dp[i][j][1] = 1;
		}
		if(check(i, j + 1, 'G') and check(i, j + 2, 'W')){
			dp[i][j][0]++;
		} 
		i--;
		j++;	
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++) cin >> a[i][j];
	}
	ll ans = 0;
	for(int i = 0; i < n; i++){
		f(i, 0);
		ans += max(dp[ii][jj][0], dp[ii][jj][1]);
//		cout << i << ' ' << ii << ' ' << jj << ' ' << max(dp[ii][jj][0], dp[ii][jj][1]) << '\n';
	}
	for(int j = 1; j < m; j++){
		f(n - 1, j);
		ans += max(dp[ii][jj][0], dp[ii][jj][1]);
	}
	cout << ans << '\n';
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -