Submission #1180918

#TimeUsernameProblemLanguageResultExecution timeMemory
1180918nguyenkhangninh99Dango Maker (JOI18_dango_maker)C++20
100 / 100
242 ms244296 KiB

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

const int maxn = 3e3 + 5;

char a[maxn][maxn];
int dp[2 * maxn][maxn][3];

signed main(){
	ios_base::sync_with_stdio(false); 
  cin.tie(0); cout.tie(0);

  int n, m; cin >> n >> m;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) cin >> a[i][j];
    }

    int ans = 0;
    for(int k = 0; k < n + m - 1; k++){
        int id = 0;
        for(int i = min(k, n - 1); 0 <= i && k - i < m; i--){
            if(id > 0){
                dp[k][id][0] = max({dp[k][id - 1][0], dp[k][id - 1][1], dp[k][id - 1][2]});
                dp[k][id][1] = max(dp[k][id - 1][0], dp[k][id - 1][1]);
                dp[k][id][2] = max(dp[k][id - 1][0], dp[k][id - 1][2]);
            }

            dp[k][id][1] += (i >= 1 && i + 1 < n && a[i - 1][k - i] == 'R' && a[i][k - i] == 'G' && a[i + 1][k - i] == 'W');
            dp[k][id][2] += (k - i >= 1 && k - i + 1 < m && a[i][k - i - 1] == 'R'&& a[i][k - i] == 'G' && a[i][k - i + 1] == 'W');

            id++;
        }

        ans += max({dp[k][id - 1][0], dp[k][id - 1][1], dp[k][id - 1][2]});
    }

    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...