제출 #962381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
962381		vjudge1	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	2032 ms	36700 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

const int N = 3010;
const string d = "RGW";

int n, m, ans;
int f[N][N], cnt[N][N];
string c[N];
vector<pair<pair<int, int>, bool>> p;

namespace Subtask1 {
	bool check() {
		return n <= 5 && m <= 5;
	}
	int len = 0;
	void dfs(int x, int num) {
		if (ans >= num + len - x + 1) return;
		if (x == len) {
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= m; j++) 
					if (cnt[i][j] > 1) return;
			ans = max(ans, num);
			return;
		}
		dfs(x + 1, num);
		if (p[x].second) {
			for (int i = p[x].first.first; i <= p[x].first.first + 2; i++) 
				cnt[i][p[x].first.second]++;
		} else {
			for (int i = p[x].first.second; i <= p[x].first.second + 2; i++) 
				cnt[p[x].first.first][i]++;
		}
		dfs(x + 1, num + 1);
		if (p[x].second) {
			for (int i = p[x].first.first; i <= p[x].first.first + 2; i++) 
				cnt[i][p[x].first.second]--;
		} else {
			for (int i = p[x].first.second; i <= p[x].first.second + 2; i++) 
				cnt[p[x].first.first][i]--;
		}
	}
	void solve() {
		for (int i = 1; i <= n; i++) 
			for (int j = 1; j <= m - 2; j++) {
				bool vis = true;
				for (int k = j; k <= j + 2; k++) 
					if (c[i][k] != d[k - j]) {
						vis = false;
						break;
					}
				if (vis) p.push_back(make_pair(make_pair(i, j), 0));
			}
		for (int j = 1; j <= m; j++) 
			for (int i = 1; i <= n - 2; i++) {
				bool vis = true;
				for (int k = i; k <= i + 2; k++) 
					if (c[k][j] != d[k - i]) {
						vis = false;
						break;
					}
				if (vis) p.push_back(make_pair(make_pair(i, j), 1));
			}
		len = p.size();
		dfs(0, 0);
		printf("%d\n", ans);
	}
}

namespace Subtask2_3 {
	void solve() {
		for (int i = 2; i <= n + m; i++) {
			int sum = 0;
			memset(f, 0, sizeof(f));
			for (int j = max(1, i - m), k = i - j; j <= n && k; j++, k--) {
				f[j][0] = max(max(f[j - 1][0], f[j - 1][1]), f[j - 1][2]);
				if (c[j][k] == 'G') {
					if (c[j - 1][k] == 'R' && c[j + 1][k] == 'W') f[j][1] = max(f[j][1], max(f[j - 1][0], f[j - 1][1]) + 1);
					if (c[j][k - 1] == 'R' && c[j][k + 1] == 'W') f[j][2] = max(f[j][2], max(f[j - 1][0], f[j - 1][2]) + 1);
				}
				sum = max(max(sum, f[j][0]), max(f[j][1], f[j][2]));
			}
			ans += sum;
		}
		printf("%d\n", ans);
	}
	
}

int main() {
//	freopen("dumpling.in", "r", stdin);
//	freopen("dumpling.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
		c[i] = " " + c[i];
	}
	if (Subtask1::check()) Subtask1::solve();
	else Subtask2_3::solve();
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~

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