Submission #313194

#TimeUsernameProblemLanguageResultExecution timeMemory
313194LucaDantasDango Maker (JOI18_dango_maker)C++17
100 / 100
823 ms221336 KiB
#include<bits/stdc++.h>
using namespace std;

constexpr int maxn = 3e3+10;

int grid[maxn][maxn], v[maxn][maxn], h[maxn][maxn], n, m;
// 0 -> no one, 1 -> vertical, 2 -> horizontal
int dp[maxn][maxn][3], diag[2*maxn];

inline int pos(int i, int j) { return m*i+j; }

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			char c; scanf(" %c", &c);
			grid[i][j] = (c=='R'?0:c=='G'?1:2);
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(i && i < n-1 && grid[i][j] == 1 && grid[i-1][j] == 0 && grid[i+1][j] == 2)
				v[i][j] = 1;
			if(j && j < m-1 && grid[i][j] == 1 && grid[i][j-1] == 0 && grid[i][j+1] == 2)
				h[i][j] = 1;
		}
	}
	// fprintf(stderr, "i j 0 1 2\n");
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			// a gente pode colocar n-1 e m-1 pq se qualquer cara tiver nos limites
			// o valor dele vai ser 0 msm
			if(i>0 && j+1<m)
				for(int x : {0, 1, 2})
					dp[i][j][0] = max(dp[i][j][0], dp[i-1][j+1][x]);
			else
				dp[i][j][0] = 0;
			if(v[i][j]) {
				if(i>0 && j+1<m)
					for(int x : {0, 1})
						dp[i][j][1] = max(dp[i][j][1], dp[i-1][j+1][x]+1);
				else
					dp[i][j][1] = 1;
			}
			if(h[i][j]) {
				if(i>0 && j+1<m)
					for(int x : {0, 2})
						dp[i][j][2] = max(dp[i][j][2], dp[i-1][j+1][x]+1);
				else
					dp[i][j][2] = 1;
			}
			// fprintf(stderr, "%d %d %d %d %d\n", i, j, dp[i][j][0], dp[i][j][1], dp[i][j][2]);
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++) {
		int here = 0;
		for(int x : {0, 1, 2})
			here = max(here, dp[i][0][x]);
		ans += here;
	}
	for(int j = 1; j < m; j++) {
		int here = 0;
		for(int x : {0, 1, 2})
			here = max(here, dp[n-1][j][x]);
		ans += here;
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:16:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |    char c; scanf(" %c", &c);
      |            ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...