Submission #680114

#	Time	Username	Problem	Language	Result	Execution time	Memory
680114		tvladm2009	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	274 ms	35756 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int) 3e3 + 7;
char a[N][N];
bool horizontal[N][N];
bool vertical[N][N];

int main()
{
#ifdef ONPC
    freopen("input.txt", "r", stdin);
#endif // ONPC

#ifndef ONPC
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC

  int n, m;
  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 = 1; j <= m; j++)
    {
      if (a[i][j] == 'G')
      {
        if (j > 1 && j < m && a[i][j - 1] == 'R' && a[i][j + 1] == 'W')
        {
          horizontal[i][j] = true;
        }
        if (i > 1 && i < n && a[i - 1][j] == 'R' && a[i + 1][j] == 'W')
        {
          vertical[i][j] = true;
        }
      }
    }
  }
  int sol = 0;
  for (int i = 2; i <= n + m; i++)
  {
    int i1 = max(1, i - m), i2 = min(n, i - 1);
    vector<vector<int>> dp(2, vector<int>(3));
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for (int lin = i1; lin <= i2; lin++)
    {
      int col = i - lin;
      dp[1][0] = max({dp[0][0], dp[0][1], dp[0][2]});
      if (horizontal[lin][col] == true)
      {
        dp[1][1] = max(dp[0][0], dp[0][1]) + 1;
      }
      else
      {
        dp[1][1] = 0;
      }
      if (vertical[lin][col] == true)
      {
        dp[1][2] = max(dp[0][0], dp[0][2]) + 1;
      }
      else
      {
        dp[1][2] = 0;
      }
      swap(dp[0], dp[1]);
    }
    sol += max({dp[0][0], dp[0][1], dp[0][2]});
  }
  cout << sol;
  return 0;
}

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