Submission #564136

#	Time	Username	Problem	Language	Result	Execution time	Memory
564136		SeDunion	Dango Maker (JOI18_dango_maker)	C++17	0 / 100	1 ms	340 KiB

dango_maker

#include <iostream>
#include <cassert>
#include <algorithm>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#ifndef LOCAL
	#include <bits/stdc++.h>
	#define cerr if(false)cerr
#endif
 
using namespace std;
using ll = long long;

const int M = 3e3 + 123;

const int N = M*3;

int x[N], y[N], dp[N][2];

int a[M][M];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1 ; i <= n ; ++ i) {
		for (int j = 1 ; j <= m ; ++ j) {
			char c;
			cin >> c;
			if (c == 'R') a[i][j] = 0;
			else if (c == 'G') a[i][j] = 1;
			else a[i][j] = 2;
		}
	}
	int ans = 0;
	for (int ij = 2 ; ij <= n + m ; ++ ij) {
		cerr << "----\n";
		cerr << ij << "\n";
		for (int i = 0 ; i <= ij + 6 ; ++ i) {
			x[i] = y[i] = 0;
		}
		int l = 4;
		for (int i = 1 ; i <= n ; ++ i) {
			int j = ij - i;
			if (j < 0 || j > m) continue;
			cerr << i << " " << j << " \n";
			l++;
			x[l] = (a[i][j] == 0 && a[i + 1][j] == 1 && a[i + 2][j] == 2);
			y[l] = (a[i][j] == 0 && a[i][j + 1] == 1 && a[i][j + 2] == 2);
			swap(x[l], y[l]);
		}
		for (int i = 0 ; i <= l ; ++ i) {
			dp[i][0] = dp[i][1] = 0;
		}
		for (int i = 4 ; i <= l ; ++ i) {
			dp[i][0] = max(dp[i][0], dp[i - 1][0] + x[i]);
			dp[i][1] = max(dp[i][1], dp[i - 1][1] + y[i]);
			dp[i][0] = max(dp[i][0], dp[i - 3][1] + x[i]);
			dp[i][1] = max(dp[i][1], dp[i - 1][0] + y[i]);
		}
		int cur = 0;
		for (int i = 1 ; i <= l ; ++ i) {
			cur = max(cur, dp[i][0]);
			cur = max(cur, dp[i][1]);
		}
		for (int i = 0 ; i <= l ; ++ i) {
			cerr << x[i] << " " << y[i] << " | " << dp[i][0] << " " << dp[i][1] << endl;
		}
	for (int i = 1 ; i <= n ; ++ i) {
		for (int j = 1 ; j <= m ; ++ j) {
			cerr << a[i][j] << " ";
		}
		cerr << "\n";
	}
		ans += cur;
		cerr << cur << "\n---\n";
	}
	cout << ans;
}

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