verify/aoj_other/aoj_2703.test.cpp

• View this file on GitHub
• Last update: 2023-05-31 02:53:46+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2703

Depends on

• icpc/dice.hpp
• icpc/template.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2703"

#include "icpc/template.hpp"
#include "icpc/dice.hpp"

void solve(int N) {
    vector paint(N, map<pair<int, int>, int>());
    REP(i, N) {
        int cx, cy;
        cin >> cx >> cy;
        vector<long long> num(6);
        REP(j, 6) cin >> num[j];
        string rot;
        cin >> rot;
        Dice dice(num);
        paint[i][{cx, cy}] = dice.d[4];
        for (auto c : rot) {
            if (c == 'L') {
                dice.xm();
                cx--;
            }
            if (c == 'R') {
                dice.xp();
                cx++;
            }
            if (c == 'F') {
                dice.ym();
                cy--;
            }
            if (c == 'B') {
                dice.yp();
                cy++;
            }
            paint[i][{cx, cy}] = dice.d[4];
        }
    }
    int N2 = 1 << N;
    vector dp(N2, 0);
    vector points(N2, set<pair<int,int>>());
    REP(bit, N2) {
        REP(i, N) {
            if (bit >> i & 1) {
                for (auto &[p, sc] : paint[i]) {
                    auto [x, y] = p;
                    points[bit].insert({x, y});
                }
            }
        }
    }
    REP(bit, N2) {
        REP(i, N) {
            if (bit >> i & 1) continue;
            int nx = 0;
            for (auto &[p, sc] : paint[i]) {
                auto [x, y] = p;
                if (points[bit].count({x, y}) == 0) {
                    nx += sc;
                }
            }
            dp[bit | (1 << i)] = max(dp[bit | (1 << i)], dp[bit] + nx);
        }
    }
    int ans = 0;
    REP(bit, N2) ans = max(ans, dp[bit]);
    cout << ans << endl;
}

int main() {
    int N;
    while (cin >> N, !(N == 0)) solve(N);
    return 0;
}

#line 1 "verify/aoj_other/aoj_2703.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2703"

#line 2 "icpc/template.hpp"

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;
template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[ ";
    for (auto& vi : v) os << vi << ", ";
    return os << "]";
}

#ifdef LOCAL
#define show(x) cerr << __LINE__ << " : " << #x << " = " << x << endl;
#else
#define show(x) true
#endif

using uint = unsigned int;
using ull = unsigned long long;

// g++ -g -fsanitize=undefined,address -DLOCAL -std=gnu++17
#line 2 "icpc/dice.hpp"

#line 4 "icpc/dice.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/2703
// d = {x-, x+, y-, y+, z-, z+}
// d = {0,  1,  2,  3,  4,  5}
struct Dice {
    vector<long long> d;
    Dice(vector<long long> &d) : d(d) {}
    void right() { d = {d[2], d[3], d[1], d[0], d[4], d[5]}; }
    void left() { REP(i, 3) right(); }
    void xm() { d = {d[5], d[4], d[2], d[3], d[0], d[1]}; }
    void xp() { REP(i, 3) xm(); }
    void ym() { d = {d[0], d[1], d[5], d[4], d[2], d[3]}; }
    void yp() { REP(i, 3) ym(); }
};
#line 5 "verify/aoj_other/aoj_2703.test.cpp"

void solve(int N) {
    vector paint(N, map<pair<int, int>, int>());
    REP(i, N) {
        int cx, cy;
        cin >> cx >> cy;
        vector<long long> num(6);
        REP(j, 6) cin >> num[j];
        string rot;
        cin >> rot;
        Dice dice(num);
        paint[i][{cx, cy}] = dice.d[4];
        for (auto c : rot) {
            if (c == 'L') {
                dice.xm();
                cx--;
            }
            if (c == 'R') {
                dice.xp();
                cx++;
            }
            if (c == 'F') {
                dice.ym();
                cy--;
            }
            if (c == 'B') {
                dice.yp();
                cy++;
            }
            paint[i][{cx, cy}] = dice.d[4];
        }
    }
    int N2 = 1 << N;
    vector dp(N2, 0);
    vector points(N2, set<pair<int,int>>());
    REP(bit, N2) {
        REP(i, N) {
            if (bit >> i & 1) {
                for (auto &[p, sc] : paint[i]) {
                    auto [x, y] = p;
                    points[bit].insert({x, y});
                }
            }
        }
    }
    REP(bit, N2) {
        REP(i, N) {
            if (bit >> i & 1) continue;
            int nx = 0;
            for (auto &[p, sc] : paint[i]) {
                auto [x, y] = p;
                if (points[bit].count({x, y}) == 0) {
                    nx += sc;
                }
            }
            dp[bit | (1 << i)] = max(dp[bit | (1 << i)], dp[bit] + nx);
        }
    }
    int ans = 0;
    REP(bit, N2) ans = max(ans, dp[bit]);
    cout << ans << endl;
}

int main() {
    int N;
    while (cin >> N, !(N == 0)) solve(N);
    return 0;
}

Back to top page