Submission #241673

#	Time	Username	Problem	Language	Result	Execution time	Memory
241673		ChrisT	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	569 ms	132856 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pib = pair<int,bool>;
using ll = long long;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#ifdef fread_unlocked
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#endif
#define mp make_pair
#define lc ind<<1
#define rc ind<<1|1
const int MN = 3e3+5, MOD = 1e9+7, BASE = 31, MASK = (1 << 13) - 1;
char grid[MN][MN]; bool canDown[MN][MN], canRight[MN][MN]; int dp[MN][MN][3];
int main () {
	int n,m,ret = 0;
	scanf ("%d %d",&n,&m);
	for (int i = 1; i <= n; i++) {
		scanf ("%s",grid[i]+1);
		for (int j = 1; j <= m-2; j++) if (grid[i][j] == 'R' && grid[i][j+1] == 'G' && grid[i][j+2] == 'W') {
			canRight[i][j+1] = 1;
		}
	}
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n-2; i++) if (grid[i][j] == 'R' && grid[i+1][j] == 'G' && grid[i+2][j] == 'W') {
			canDown[i+1][j] = 1;
		}
	}
	for (int v = 2; v <= n+m; v++) { // i + j = v
		int add = 0;
		for (int i = 1; i <= n; i++) {
			int j = v - i;
			if (1 <= j && j <= m) {
				dp[i][j][0] = max({dp[i-1][j+1][0],dp[i-1][j+1][1],dp[i-1][j+1][2]});
				if (canRight[i][j]) dp[i][j][1] = max(dp[i-1][j+1][0],dp[i-1][j+1][1]) + 1; 
				if (canDown[i][j]) dp[i][j][2] = max(dp[i-1][j+1][0],dp[i-1][j+1][2]) + 1;
				add = max({add,dp[i][j][0],dp[i][j][1],dp[i][j][2]});
			}
		}
		ret += add;
	}
	printf ("%d\n",ret);
	return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&n,&m);
  ~~~~~~^~~~~~~~~~~~~~~
dango_maker.cpp:21:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%s",grid[i]+1);
   ~~~~~~^~~~~~~~~~~~~~~~

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