Submission #312520

#	Time	Username	Problem	Language	Result	Execution time	Memory
312520		quocnguyen1012	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	713 ms	181536 KiB

dango_maker

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 3005;

int N, M;
char c[maxn][maxn];
int f[maxn][3];
int can[maxn][maxn][2];
vector<ii> same[2 * maxn];

signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
  freopen("A.INP", "r", stdin);
  freopen("A.OUT", "w", stdout);
#endif // LOCAL

  cin >> N >> M;
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= M; ++j) {
      cin >> c[i][j];
      same[i + j].eb(i, j);
    }
  }
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= M; ++j) {
      if (c[i - 1][j] == 'R' && c[i][j] == 'G' && c[i + 1][j] == 'W')
        can[i][j][1] = 1;
      if (c[i][j - 1] == 'R' && c[i][j] == 'G' && c[i][j + 1] == 'W')
        can[i][j][2] = 1;
    }
  }
  int res = 0;
  for (int cr = 1; cr <= N + M; ++cr) {
    memset(f, 0, sizeof f);
    int n = same[cr].size();
    for (int i = 1; i <= n; ++i) {
      int x = same[cr][i - 1].fi, y = same[cr][i - 1].se;
      f[i][0] = max({f[i - 1][0], f[i - 1][1], f[i - 1][2]});
      for (int j = 1; j <= 2; ++j)
        if (can[x][y][j]) {
          f[i][j] = max(f[i - 1][0], f[i - 1][j]) + 1;
        }
    }
    res += max({f[n][0], f[n][1], f[n][2]});
  }
  cout << res;

}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:52:24: warning: iteration 1 invokes undefined behavior [-Waggressive-loop-optimizations]
   52 |         if (can[x][y][j]) {
      |             ~~~~~~~~~~~^
dango_maker.cpp:51:25: note: within this loop
   51 |       for (int j = 1; j <= 2; ++j)
      |                       ~~^~~~
dango_maker.cpp:41:20: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   41 |         can[i][j][2] = 1;
      |         ~~~~~~~~~~~^
dango_maker.cpp:52:24: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
   52 |         if (can[x][y][j]) {
      |             ~~~~~~~~~~~^

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