Submission #233675

#TimeUsernameProblemLanguageResultExecution timeMemory
233675Coroian_DavidDango Maker (JOI18_dango_maker)C++11
13 / 100
5 ms384 KiB
#include <bits/stdc++.h> #define MAX_N 3000 #define MAX_M 3000 using namespace std; int a[MAX_N + 1][MAX_M + 1]; int lin[MAX_N + 1][MAX_M + 1]; int col[MAX_N + 1][MAX_M + 1]; int dp[MAX_N + 1][MAX_M + 1]; int n, m; int rez; string s; void readFile() { cin >> n >> m; for(int i = 1; i <= n; i ++) { cin >> s; for(int j = 1; j <= m; j ++) a[i][j] = (s[j - 1] == 'R' ? 0 : (s[j - 1] == 'G' ? 1 : 2)); } } void getLin() { for(int i = 1; i <= n; i ++) { for(int j = 3; j <= m; j ++) { lin[i][j] = lin[i][j - 1]; if(a[i][j - 2] == 0 && a[i][j - 1] == 1 && a[i][j] == 2) lin[i][j] = max(lin[i][j], lin[i][j - 3] + 1); } } } void getCol() { for(int j = 1; j <= m; j ++) { for(int i = 3; i <= n; i ++) { col[i][j] = col[i - 1][j]; if(a[i - 2][j] == 0 && a[i - 1][j] == 1 && a[i][j] == 2) col[i][j] = max(col[i][j], col[i - 3][j] + 1); } } } void getDp() { for(int i = 1; i <= n; i ++) dp[i][1] = col[i][1]; for(int j = 1; j <= m; j ++) dp[1][j] = lin[1][j]; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { if(i + 1 <= n) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + lin[i + 1][j]); if(j + 1 <= m) dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + col[i][j + 1]); } } rez = dp[n][m]; } void solve() { getLin(); getCol(); getDp(); } void printFile() { cout << rez << "\n"; } int main() { readFile(); solve(); printFile(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...