結果
問題 | No.2178 Payable Magic Items |
ユーザー |
|
提出日時 | 2023-01-06 22:15:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,548 ms / 4,000 ms |
コード長 | 1,412 bytes |
コンパイル時間 | 2,011 ms |
コンパイル使用メモリ | 206,980 KB |
最終ジャッジ日時 | 2025-02-10 00:02:11 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#ifndef hari64#include <bits/stdc++.h>// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#define debug(...)#else#include "viewer.hpp"#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)#endif // clang-format offusing namespace std;constexpr int INF=1001001001;constexpr long long INFll=1001001001001001001;template<class T>bool chmax(T&a,const T&b){return a<b?a=b,1:0;}template<class T>bool chmin(T&a,const T&b){return a>b?a=b,1:0;} // clang-format onint main() {cin.tie(0);ios::sync_with_stdio(false);int N, K;cin >> N >> K;set<string> Ss;for (int i = 0; i < N; i++) {string S;cin >> S;Ss.insert(S);}int ans = 0;map<string, bool> memo;auto dfs = [&](const auto &f, string X) -> bool {if (memo.find(X) != memo.end()) return memo[X];bool has_larger = false;for (int d = 0; d < K; d++) {if (X[d] != '4') {X[d]++;has_larger |= f(f, X);X[d]--;}}// debug(X, has_larger);if (Ss.find(X) != Ss.end()) {if (has_larger) {ans++;}has_larger = true;}return memo[X] = has_larger;};dfs(dfs, string(K, '0'));cout << ans << endl;return 0;}