제출 #122493

#제출 시각아이디문제언어결과실행 시간메모리
122493egorlifarDango Maker (JOI18_dango_maker)C++17
100 / 100
752 ms171128 KiB
/* ЗАПУСКАЕМ ░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░ ▄███▀░◐░░░▌░░░░░░░ ░░░░▌░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▌░░░░░▐▄▄░░░░░ ░░░░▌░░░░▄▀▒▒▀▀▀▀▄ ░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄ ░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░▄▄▌▌▄▌▌░░░░░ */ #include <iostream> #include <complex> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <numeric> #include <cstring> #include <ctime> #include <cstdlib> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <list> #include <cmath> #include <bitset> #include <cassert> #include <queue> #include <stack> #include <deque> using namespace std; template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; } template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; } template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; } template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; } template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; } template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; } template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; } template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; } template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; } template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; } template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; } #define sz(c) (int)(c).size() #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define left left228 #define right right228 #define next next228 #define rank rank228 #define prev prev228 #define y1 y1228 #define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin) #define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout) #define files(FILENAME) read(FILENAME), write(FILENAME) #define pb push_back const string FILENAME = "input"; const int MAXN = 3228; int n, m; string s[MAXN]; int dp[MAXN][MAXN][4]; int get(int i, int j, int t) { if (i < 0 || s[i][j] != 'R') { return 0; } if (dp[i][j][t] != -1) { return dp[i][j][t]; } int res = 0; chkmax(res, get(i - 1, j + 1, (t * 2) % 4)); chkmax(res, get(i - 2, j + 2, 0)); if (s[i][j] == 'R' && s[i + 1][j] == 'G' && s[i + 2][j] == 'W' && t == 0) { chkmax(res, get(i - 1, j + 1, 0) + 1); chkmax(res, get(i - 2, j + 2, 0) + 1); } if (s[i][j] == 'R' && s[i][j + 1] == 'G' && s[i][j + 2] == 'W') { chkmax(res, get(i - 1, j + 1, (t * 2 + 1) % 4) + 1); chkmax(res, get(i - 2, j + 2, 2) + 1); } dp[i][j][t] = res; return res; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //read(FILENAME); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> s[i]; } for (int i = 0; i <= n + 2; i++) { for (int j = 0; j <= m + 2; j++) { for (int k = 0; k < 4; k++) { dp[i][j][k] = -1; } } } int ans = 0; for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j >= 0; j--) { if (dp[i][j][0] == -1) { ans += get(i, j, 0); } } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...