Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<algorithm>
- #include<vector>
- #include<unordered_map>
- #include<array>
- #include<functional>
- #include<cstring>
- #include<stack>
- #include<queue>
- #define endl '\n'
- using namespace std;
- using ll = long long;
- template<typename T> using F = function<T>;
- template<typename T> using V = vector<T>;
- template<typename T, size_t size> using A = array<T, size>;
- template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
- void _debug() {cerr << endl;}
- template<typename T, typename... Args>
- void _debug(const T& a, Args... b) {cerr << a << ' ', _debug(b...);}
- #define debug(...) cerr<<'('<<#__VA_ARGS__<<"): ", _debug(__VA_ARGS__)
- template<typename T>
- ostream& operator<<(ostream& os, const V<T>& v) {
- for (const auto& i : v)
- os << i << ' ';
- return os;
- }
- template<typename T, size_t size>
- ostream& operator<<(ostream& os, const A<T, size>& a) {
- for (auto i : a)
- os << i << ' ';
- return os;
- }
- constexpr int inf = 0x3f3f3f3f;
- constexpr ll infll = (ll)inf << 32 | inf;
- int table[256];
- inline void init() {
- table['B'] = 0, table['G'] = 1, table['R'] = 2, table['Y'] = 3;
- }
- using block = A<P<int>, 4>;
- istream& operator>>(istream& is, block& b) {
- char color, num;
- for (int i = 0; i < 4; i++)
- is >> color >> num, b[i] = {table[(int)color], num - '0'};
- return is;
- }
- int comp(int a, int b, int c, int d) {
- if (a > b) {swap(a, b);} if (b > c) {swap(b, c);} if (c > d) {swap(c, d);}
- if (a > b) {swap(a, b);} if (b > c) {swap(b, c);} if (a > b) {swap(a, b);}
- return a << 6 | b << 4 | c << 2 | d;
- }
- tuple<int, int, int, int> extr(int cond) {
- return {(cond >> 6) & 3, (cond >> 4) & 3, (cond >> 2) & 3, cond & 3};
- }
- int dp[2][256], s[2][256], stop[2];
- bool ins[2][256];
- inline void solve() {
- for (int k = 0; k < 2; k++)
- for (int i = 0; i < 256; i++)
- dp[k][i] = ~inf;
- int n, ans = ~inf; cin >> n;
- block curb; cin >> curb;
- int cond = comp(curb[0].first, curb[1].first, curb[2].first, curb[3].first);
- dp[0][cond] = 0, ins[0][cond] = true, s[0][stop[0]++] = cond;
- for (int k = 0; k + 1 < n; k++) {
- cin >> curb;
- int sum = 0;
- for (int i = 0; i < 4; i++)
- sum += curb[i].second;
- while (stop[k & 1]) {
- int cond = s[k & 1][--stop[k & 1]], cur = dp[k & 1][cond], a, b, c, d;
- tie(a, b, c, d) = extr(cond), ins[k & 1][cond] = false, dp[k & 1][cond] = ~inf;
- dp[~k & 1][cond] = max(dp[~k & 1][cond], cur - sum);
- if (!ins[~k & 1][cond])
- ins[~k & 1][s[~k & 1][stop[~k & 1]++] = cond] = true;
- for (int* e : {&a, &b, &c, &d})
- for (int i = 0; i < 4; i++) {
- int x, y; tie(x, y) = curb[i];
- if (x != *e) continue;
- int tmp = *e; *e = curb[(i + 2) & 3].first;
- switch (x) {
- case 0: y = sum - y; break;
- case 1: y = sum + y; break;
- case 2: y = sum * y; break;
- case 3: y = sum / y; break;
- }
- int next = comp(a, b, c, d);
- dp[~k & 1][next] = max(dp[~k & 1][next], cur + y);
- if (!ins[~k & 1][next])
- ins[~k & 1][s[~k & 1][stop[~k & 1]++] = next] = true;
- *e = tmp;
- }
- }
- }
- while (stop[~n & 1]) {
- int cond = s[~n & 1][--stop[~n & 1]];
- ans = max(ans, dp[~n & 1][cond]);
- }
- cout << ans << endl;
- }
- signed main() {
- // cin.tie(nullptr)->sync_with_stdio(false);
- int T = 1;
- cin >> T;
- init();
- while (T--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement