Submission #208337

#	Time	Username	Problem	Language	Result	Execution time	Memory
208337		opukittpceno_hhr	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	539 ms	44536 KiB

dango_maker

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>
 
using namespace std;
 
const int N = 3001;
 
int a[N][N];
 
int read() {
	char c;
	cin >> c;
	if (c == 'R') return 0;
	if (c == 'G') return 1;
	if (c == 'W') return 2;
	assert(false);
	return -1;
}
 
int n, m;
 
int ok(int i, int j, int dir) {
	if (dir == 0) {
		if (i == 0 || i + 1 == n) return 0;
		return a[i - 1][j] == 0 && a[i][j] == 1 && a[i + 1][j] == 2;
	} else {
		if (j == 0 || j + 1 == m) return 0;
		return a[i][j - 1] == 0 && a[i][j] == 1 && a[i][j + 1] == 2;
	}
}

int dp[3];
int ndp[3];

//0 - none
//1 - up
//2 - left

void rec(int cu, int cd) {
	ndp[0] = max({dp[0], dp[1], dp[2]});
	ndp[1] = max({dp[0], dp[1]}) + cu;
	ndp[2] = max({dp[0], dp[2]}) + cd;
	for (int i = 0; i < 3; i++) {
		dp[i] = ndp[i];
		ndp[i] = 0;
	}
}

void init() {
	fill(dp, dp + 3, 0);
	fill(ndp, ndp + 3, 0);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			a[i][j] = read();
		}
	}
	int ans = 0;
	for (int sm = 0; sm <= n + m; sm++) {
		init();
		for (int i = 0; i < n; i++) {
			int j = sm - i;
			if (j < 0 || j >= m) continue;
			rec(ok(i, j, 0), ok(i, j, 1));
		}
		ans += max({dp[0], dp[1], dp[2]});
	}
	cout << ans << endl;
}

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