Submission #916585

#TimeUsernameProblemLanguageResultExecution timeMemory
916585vjudge1Dango Maker (JOI18_dango_maker)C++11
100 / 100
416 ms124648 KiB
#include <iostream>
using namespace std;

int N, M, ans;
char a[3010][3010];
int dp[3010][3010][3];

bool ver(int x, int y) {
  return a[x-1][y]=='R' && a[x][y]=='G' && a[x+1][y]=='W';
}

bool hor(int x, int y) {
  return a[x][y-1]=='R' && a[x][y]=='G' && a[x][y+1]=='W';
}


int main() 
{
  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<=N; i++) {
    for(int j=M; j>=1; j--) {
      dp[i][j][0] = max(dp[i-1][j+1][0], max(dp[i-1][j+1][1], dp[i-1][j+1][2]));
      dp[i][j][1] = (!ver(i,j) ? int(-1e9) : 1 + max(dp[i-1][j+1][0], dp[i-1][j+1][1]));
      dp[i][j][2] = (!hor(i,j) ? int(-1e9) : 1 + max(dp[i-1][j+1][0], dp[i-1][j+1][2]));
    }
  }
  for(int i=1; i<=N; i++) {
    for(int j=1; j<=M; j++) {
      if (i==N || j==1) {
        ans += max(dp[i][j][0], max(dp[i][j][1], dp[i][j][2]));
      }
    }
  }
  cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...