Submission #364973

#	Time	Username	Problem	Language	Result	Execution time	Memory
364973		tushar_2658	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	442 ms	221804 KiB

dango_maker

#include "bits/stdc++.h"
using namespace std;

const int maxn = 3005;
using ll = long long;

char s[maxn][maxn];
int n, m;
ll dp[maxn][maxn][3];
ll corner[maxn + maxn];

int main(int argc, char const *argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> m;
  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= m; ++j){
      cin >> s[i][j];
      if(s[i][j] == 'R')s[i][j] = 'A';
      else if(s[i][j] == 'G')s[i][j] = 'B';
      else s[i][j] = 'C';
    } 
  }

  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= m; ++j){
      dp[i][j][0] = max({dp[i - 1][j + 1][0], dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]});
      if(s[i][j] == 'B'){
        if(s[i][j - 1] == 'A' && s[i][j + 1] == 'C'){
          dp[i][j][1] = max({dp[i][j][1], dp[i - 1][j + 1][0] + 1, dp[i - 1][j + 1][1] + 1});
        }
        if(s[i + 1][j] == 'C' && s[i - 1][j] == 'A'){
          dp[i][j][2] = max({dp[i][j][2], dp[i - 1][j + 1][0] + 1, dp[i - 1][j + 1][2] + 1});
        }
      }
      corner[i + j] = max({corner[i + j], dp[i][j][1], dp[i][j][2], dp[i][j][0]});
    }
  }
  ll ans = 0;
  for(int i = 1; i <= n + m; ++i){
    ans += corner[i];
  }
  cout << ans << '\n';

  return 0;
}

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