結果
問題 | No.2178 Payable Magic Items |
ユーザー | pixy |
提出日時 | 2023-01-06 23:27:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 424 ms / 4,000 ms |
コード長 | 3,974 bytes |
コンパイル時間 | 2,553 ms |
コンパイル使用メモリ | 184,560 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-05-08 13:40:07 |
合計ジャッジ時間 | 4,938 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
5,248 KB |
testcase_01 | AC | 6 ms
5,376 KB |
testcase_02 | AC | 7 ms
5,376 KB |
testcase_03 | AC | 8 ms
5,376 KB |
testcase_04 | AC | 7 ms
5,376 KB |
testcase_05 | AC | 7 ms
5,376 KB |
testcase_06 | AC | 7 ms
5,376 KB |
testcase_07 | AC | 6 ms
5,376 KB |
testcase_08 | AC | 7 ms
5,376 KB |
testcase_09 | AC | 7 ms
5,376 KB |
testcase_10 | AC | 6 ms
5,376 KB |
testcase_11 | AC | 424 ms
11,008 KB |
testcase_12 | AC | 89 ms
11,008 KB |
testcase_13 | AC | 100 ms
11,008 KB |
testcase_14 | AC | 90 ms
11,136 KB |
testcase_15 | AC | 92 ms
11,008 KB |
testcase_16 | AC | 91 ms
11,008 KB |
testcase_17 | AC | 60 ms
6,784 KB |
testcase_18 | AC | 7 ms
5,376 KB |
testcase_19 | AC | 24 ms
6,272 KB |
testcase_20 | AC | 7 ms
5,376 KB |
testcase_21 | AC | 7 ms
5,376 KB |
testcase_22 | AC | 7 ms
5,376 KB |
testcase_23 | AC | 7 ms
5,376 KB |
testcase_24 | AC | 75 ms
9,088 KB |
testcase_25 | AC | 30 ms
5,632 KB |
testcase_26 | AC | 32 ms
6,784 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; // #include <atcoder/all> // using namespace atcoder; using ll = long long; const ll MOD = 998'244'353; //const ll MOD = 1000'000'007; const ll INF = (1LL<<30)-1; const ll LINF = (1LL<<62)-1; //#define _GLIBCXX_DEQUE_BUF_SIZE 512 // int:[-2'147'483'648 : 2'147'483'647] // ll:[-9'223'372'036'854'775'808 : 9'223'372'036'854'775'807] #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define repi(i, a, n) for (ll i = a; i < (ll)(n); i++) #define pb(a) push_back(a) #define PS(a) cout<<(a)<<" "; #define PL(a) cout<<(a)<<endl; #define endl "\n" //#define ONLINE_JUDGE 1 #ifdef ONLINE_JUDGE #define ES(a) while(0){} #define EL(a) while(0){} #else #define NAME(a) #a #define ES(a) cerr<<NAME(a)<<": "<<(a)<<" "; #define EL(a) cerr<<NAME(a)<<": "<<(a)<<endl; #endif #define END(a) {PL(a) return;} #define RES(a) cerr<<"\r"<<NAME(a)<<": "<<(a)<<" "; #define fi first #define se second #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(),(a).rend() #define SORT(a) sort(a.begin(), a.end()); #define REVERSE(a) reverse(a.begin(), a.end()); #define ERASE(a) a.erase(unique(a.begin(), a.end()), a.end()); using Pii = pair<int, int>; using Pll = pair<ll,ll>; template <class T> using V = vector<T>; template<typename T >ostream &operator<<(ostream &os, const vector< T > &v) {for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != (int) v.size() ? " " : "");}return os;} template<typename T >istream &operator>>(istream &is, vector< T > &v) {for(T &in : v) is >> in;return is;} template<typename T, typename U > ostream &operator<<(ostream &os, const pair<T,U> &p) {os << p.first << ' ' << p.second; return os;} template<typename T, typename U > istream &operator>>(istream &is, pair<T,U> &p) { is >> p.first >> p.second; return is;} template<typename T, unsigned long int sz > ostream &operator<<(ostream &os, const array< T , sz > &v) {for(int i = 0; i < sz; i++) {os << v[i] << (i + 1 != (int) v.size() ? " " : "");}return os;} template<typename T, unsigned long int sz > istream &operator>>(istream &is, array< T , sz > &v) {for(T& in:v){cin>>in;} return is;} template<class T, class U > void chmin(T& t, const U& u) {if (t > u) t = u;} template<class T, class U > void chmax(T& t, const U& u) {if (t < u) t = u;} void solve() { ll N,K; cin>>N>>K; V<string> S(N); cin>>S; rep(i,N) S[i] += string(8-K,'0'); sort(RALL(S)); K = 8; V<ll> pos(K); //8 int dp[5][5][5][5][5][5][5][5]; auto dfs = [&](auto dfs, int d)->void { if(d==K){ dp[pos[0]][pos[1]][pos[2]][pos[3]][pos[4]][pos[5]][pos[6]][pos[7]] = 0; return; } rep(i,5){ pos[d] = i; dfs(dfs, d+1); } }; dfs(dfs,0); rep(i,N){ rep(j,K) pos[j] = S[i][j]-'0'; if(dp[pos[0]][pos[1]][pos[2]][pos[3]][pos[4]][pos[5]][pos[6]][pos[7]]==-1) continue; auto dfs2 = [&](auto dfs2, int d)->void { if(d==K){ dp[pos[0]][pos[1]][pos[2]][pos[3]][pos[4]][pos[5]][pos[6]][pos[7]] = -1; return; } for(ll k=S[i][d]-'0';k>=0;k--){ pos[d] = k; dfs2(dfs2, d+1); } }; dfs2(dfs2,0); rep(j,K) pos[j] = S[i][j]-'0'; dp[pos[0]][pos[1]][pos[2]][pos[3]][pos[4]][pos[5]][pos[6]][pos[7]]=1; } ll ans = 0; auto dfs3 = [&](auto dfs3, int d)->void { if(d==K){ if(dp[pos[0]][pos[1]][pos[2]][pos[3]][pos[4]][pos[5]][pos[6]][pos[7]]==1) ans++; return; } rep(i,5){ pos[d] = i; dfs3(dfs3, d+1); } }; dfs3(dfs3,0); PL(N-ans) return; } int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(15); int TT = 1; //cin>>TT; for(int tt = 0; tt<TT; tt++) solve(); return 0; }