This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define FOR(i,s,e) for(int i=(s);i<(int)(e);i++)
#define FOE(i,s,e) for(int i=(s);i<=(int)(e);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(), (x).end()
#define CLR(s) memset(s,0,sizeof(s))
#define PB push_back
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pll;
typedef map<int,int> mii;
typedef vector<int> vi;
const int MX_N = 3333;
int DP[MX_N * 2][MX_N][2];
bool v[MX_N][MX_N];
bool h[MX_N][MX_N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
string S[N]; REP(i, N) cin >> S[i];
FOR(i, 2, N) REP(j, M) v[i][j] = (string("") + S[i - 2][j] + S[i - 1][j] + S[i][j] == "RGW");
FOR(j, 2, M) REP(i, N) h[i][j] = (string("") + S[i][j - 2] + S[i][j - 1] + S[i][j] == "RGW");
FOE(k, 0, N + M - 2) FOR(i, 0, N) {
int j = k - i;
if (i > 0) {
DP[k][i][0] = DP[k][i - 1][0];
DP[k][i][1] = max(DP[k][i - 1][1], DP[k][i - 1][0]);
}
if (i >= 3) {
DP[k][i][0] = max(DP[k][i][0], DP[k][i - 3][1]);
}
if (j >= 0 && j < M) {
DP[k][i][0] += (int) v[i][j]; // [i][j] = end of vertical
DP[k][i][1] += (int) h[i][j]; // [i][j] = end of horizontal
}
}
int Ans = 0;
FOE(k, 0, N + M - 2)
Ans += max(DP[k][N - 1][1], DP[k][N - 1][0]);
cout << Ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |