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 <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
// #define int ll
using namespace std;
typedef long long ll;
signed main() {
#ifdef PC
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, cnt = 0, ans = 0;
cin >> n >> m;
vector<vector<char>> mat(n, vector<char> (m));
vector<vector<bool>> hor(n, vector<bool> (m, 0));
vector<vector<bool>> ver(n, vector<bool> (m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mat[i][j];
}
}
for (int i = 0; i < n - 2; i++) {
for (int j = 0; j < m; j++) {
if(!(mat[i][j] == 'R' && mat[i + 1][j] == 'G' && mat[i + 2][j] == 'W'))
continue;
ver[i][j] = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 2; j++) {
if(!(mat[i][j] == 'R' && mat[i][j + 1] == 'G' && mat[i][j + 2] == 'W'))
continue;
hor[i][j] = 1;
}
}
for (int nn = 0; nn < n + m; nn++) {
int i1, j1;
if(nn < n) {
i1 = nn, j1 = 0;
}
else {
i1 = n - 1, j1 = nn - i1;
}
vector<pair<int, int>> now;
while(i1 >= 0 && j1 < m) {
// cout << "(" << i1 << ", " << j1 << ") ";
now.pb({ver[i1][j1], hor[i1][j1]});
i1--, j1++;
}
// cout << endl;
reverse(now.begin(), now.end());
int nr = len(now);
vector<vector<int>> dp(nr + 1, vector<int> (3, 0));
for (int i = 0; i < nr; i++) {
for (int j = 0; j < 3; j++) {
dp[i + 1][j] = dp[i][max(j - 1, 0)];
if(now[i].sc)
dp[i + 1][j] = max(dp[i + 1][j], 1 + dp[i][2]);
if(j == 0 && now[i].ft)
dp[i + 1][j] = max(dp[i + 1][j], 1 + dp[i][0]);
}
}
ans += dp[nr][0];
}
cout << ans << endl;
}
Compilation message (stderr)
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:32:12: warning: unused variable 'cnt' [-Wunused-variable]
int n, m, cnt = 0, ans = 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... |