Submission #916585

#	Time	Username	Problem	Language	Result	Execution time	Memory
916585		vjudge1	Dango Maker (JOI18_dango_maker)	C++11	100 / 100	416 ms	124648 KiB

dango_maker

#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;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67