Submission #62226

#	Time	Username	Problem	Language	Result	Execution time	Memory
62226		kingpig9	Dango Maker (JOI18_dango_maker)	C++11	100 / 100	201 ms	113084 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 3010;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

void setmax (int &a, int b) {
	if (a < b) {
		a = b;
	}
}

int N, M;
char S[MAXN][MAXN];
int dp[MAXN][3];	//0: none. 1: vert. 2: horiz.

int main() {
	//The biggest hint: GO BY DIAGONALS not by horizontal/vertical.
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		scanf("%s", S[i] + 1);
	}

	int ans = 0;
	for (int sum = 2; sum <= N + M; sum++) {
		//try to choose if you can!
		//1 <= i <= N, 1 <= sum - i <= M
		//1 <= i <= N, sum - M <= i <= sum - 1
		//max(1, sum - M) <= i <= min(N, sum - 1)

		int xmn = max(1, sum - M), xmx = min(N, sum - 1);
		fillchar(dp, -2);
		dp[xmn - 1][0] = 0;

		for (int x = xmn; x <= xmx; x++) {
			int y = sum - x;
			//add one if can
			if (S[x][y] == 'G') {
				//vertical
				if (S[x - 1][y] == 'R' && S[x + 1][y] == 'W') {
					//cur is 1. prev can't be 2.
					dp[x][1] = max(dp[x - 1][0], dp[x - 1][1]) + 1;
				}

				if (S[x][y - 1] == 'R' && S[x][y + 1] == 'W') {
					//cur is 2. prev can't be 1.
					dp[x][2] = max(dp[x - 1][0], dp[x - 1][2]) + 1;
				}
			}

			//otherwise not add one
			dp[x][0] = max({dp[x - 1][0], dp[x - 1][1], dp[x - 1][2]});
		}
		ans += max({dp[xmx][0], dp[xmx][1], dp[xmx][2]});
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:26:7: 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:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S[i] + 1);
   ~~~~~^~~~~~~~~~~~~~~~

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