Submission #1032537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032537		juicy	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	214 ms	18208 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3005;

int n, m;
int ver[N], hor[N];
char a[N][N];
bool up[N], rt[N];

int solve(int N) {
	for (int i = 1; i <= N; ++i) {
		ver[i] = ver[i - 1];
		hor[i] = hor[i - 1];
		if (i > 1) {
			hor[i] = max(hor[i], ver[i - 2]);
			ver[i] = max(ver[i], hor[i - 2]);
		}
		ver[i] += up[i] && rt[i + 1];
		hor[i] += up[i + 1] && rt[i];
	}
	return max(ver[N], hor[N]);
}

bool inside(int i, int j, char c) {
	return 1 <= i && i <= n && 1 <= j && j <= m && a[i][j] == c;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> a[i][j];
		}
	}
	int res = 0;
	for (int it = 1; it <= n + m + 1; ++it) {
		vector<int> cands;
		for (int j = 1; j < it; ++j) {
			if (inside(it - j, j, 'G')) {
				cands.push_back(j);
			}
 		}
		reverse(cands.begin(), cands.end());
		for (int i = 0; i < cands.size(); ) {
			int j = i;
			while (j < cands.size() && cands[i] - cands[j] == j - i) {
				++j;
			}
			for (int k = i; k < j; ++k) {
				up[k - i + 1] = inside(it - cands[k] - 1, cands[k], 'R');
				rt[k - i + 1] = inside(it - cands[k], cands[k] + 1, 'W');
			}
			up[j - i + 1] = inside(it - cands[j - 1], cands[j - 1] - 1, 'R');
			rt[j - i + 1] = inside(it - cands[j - 1] + 1, cands[j - 1], 'W');
			res += solve(j - i);
			i = j;
		}
	}
	cout << res;
	return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i = 0; i < cands.size(); ) {
      |                   ~~^~~~~~~~~~~~~~
dango_maker.cpp:56:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    while (j < cands.size() && cands[i] - cands[j] == j - i) {
      |           ~~^~~~~~~~~~~~~~

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