結果

問題 No.2178 Payable Magic Items
ユーザー mine691
提出日時 2022-09-27 01:56:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,361 bytes
コンパイル時間 2,173 ms
コンパイル使用メモリ 201,888 KB
最終ジャッジ日時 2025-02-07 16:40:38
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2 RE * 2
other WA * 1 RE * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using Int = long long;
constexpr static int mod = 1e9 + 7;
constexpr static int inf = (1 << 30) - 1;
constexpr static Int infll = (1LL << 61) - 1;
int Competitive_Programming = (ios_base::sync_with_stdio(false), cin.tie(nullptr), cout << fixed << setprecision(15), 0);
#pragma region Debug Template
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s)
{
    return '"' + s + '"';
}
string to_string(const char *s)
{
    return to_string((string)s);
}
string to_string(bool b)
{
    return (b ? "true" : "false");
}
string to_string(vector<bool> v)
{
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++)
    {
        if (!first)
        {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}
template <size_t N>
string to_string(bitset<N> v)
{
    string res = "";
    for (size_t i = 0; i < N; i++)
    {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}
template <typename A>
string to_string(A v)
{
    bool first = true;
    string res = "{";
    for (const auto &x : v)
    {
        if (!first)
        {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p)
{
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p)
{
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p)
{
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << " " << to_string(H);
    debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
#pragma endregion
int enc(string s)
{
    int ret = 0;
    for (int i = 0; i < s.size(); i++)
    {
        ret *= 4;
        ret += s[i] - 'A';
    }
    return ret;
}
int dfs(string &s, vector<int> &dp, vector<int> &mp, vector<int> &used)
{
    int e = enc(s);
    if (dp[e] != -1)
    {
        int ret = (used[e] ? 0 : dp[e] + mp[e]);
        // dp[e] = 0;
        used[e] = 1;
        return ret;
    }
    // used[e] = 1;
    int ret = 0, K = s.size();
    for (int i = 0; i < K; i++)
    {
        if (s[i] == 'D')
            continue;
        s[i]++;
        ret += dfs(s, dp, mp, used);
        if(used[enc(s)] == 0 and mp[enc(s)] == 1)
            ret++;
        used[enc(s)] = 1;
        s[i]--;
    }
    dp[e] = ret;
    // debug_out(s, dp[e], e);
    return ret;
}
int main()
{
    int N, K;
    cin >> N >> K;
    vector<string> s(N);
    vector<int> mp(1 << (2 * K));
    for (int i = 0; i < N; i++)
    {
        cin >> s[i];
        mp[enc(s[i])]++;
        // debug_out(s[i], enc(s[i]));
    }
    vector<int> used(1 << (2 * K)), dp(1 << (2 * K), -1);
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        int t = dfs(s[i], dp, mp, used);
        ans += t;
        // debug_out(s[i], t);
        dp[enc(s[i])] = 0;
    }
    cout << ans << endl;
    // debug_out(mp, dp);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0