fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //defines
  5. #define openin freopen("input.txt","r",stdin)
  6. #define openout freopen("output.txt","w",stdout)
  7. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  8. #define ll long long
  9. #define int long long
  10. #define mod 1000000007
  11. #define repr(i,x,y) for (__typeof(x) i=x;i>=y;i--)
  12. #define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++)
  13. #define all(c) (c).begin(),(c).end()
  14. #define ff first
  15. #define ss second
  16. #define pb push_back
  17. #define mp make_pair
  18.  
  19. /* Print pair */
  20. template <typename T,typename S>
  21. ostream & operator << (ostream &os , const pair<T,S> &v) {
  22.     os << "(" ;
  23.     os << v.first << "," << v.second << ")" ;
  24.     return os ;
  25. }
  26. /* Print vector */
  27. template <typename T>
  28. ostream & operator << (ostream &os , const vector<T> &v) {
  29.     os << "[" ;
  30.     int sz = v.size() ;
  31.     for(int i = 0 ; i < sz ; ++i) {
  32.         os << v[i] ;
  33.         if(i!=sz-1)os << "," ;
  34.     }
  35.     os << "]\n" ;
  36.     return os ;
  37. }
  38. /* Print set */
  39. template <typename T>
  40. ostream & operator << (ostream &os , const set<T> &v) {
  41.     T last = *v.rbegin() ;
  42.     os << "[" ;
  43.     for(auto it : v) {
  44.         os << it  ;
  45.         if(it != last) os << "," ;
  46.     }
  47.     os << "]\n" ;
  48.     return os ;
  49. }
  50. /* Print Map */
  51. template <typename T,typename S>
  52. ostream & operator << (ostream &os , const map<T,S> &v) {
  53.     for(auto it : v) {
  54.         os << it.first << " : " << it.second << "\n" ;
  55.     }
  56.     return os ;
  57. }
  58. int power(int a , int b)
  59. {
  60.     int res = 1 ;
  61.     while(b)
  62.     {
  63.         if(b%2) {
  64.             res = (res * a) % mod ;
  65.         }
  66.         b/=2 ;
  67.         a = (a*a) % mod ;
  68.     }
  69.     return res ;
  70. }
  71.  
  72. //debug
  73. #define TRACE
  74.  
  75. #ifdef TRACE
  76. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  77. template <typename Arg1>
  78. void __f(const char* name, Arg1&& arg1){
  79. 		cerr << name << " : " << arg1 << std::endl;
  80. }
  81. template <typename Arg1, typename... Args>
  82. void __f(const char* names, Arg1&& arg1, Args&&... args){
  83. 		const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  84. }
  85. #else
  86. #define trace(...)
  87. #endif
  88.  
  89. const int N = 111 ;
  90. string arr[N] ;
  91. string forbid[N] ;
  92. int cnt[2][N] ;
  93. int n , m , p ;
  94. map<pair<int,vector<int> > , int> dp ;
  95.  
  96. int solve(int idx , vector<int> &temp) {
  97.     if(idx == p) {
  98.         if(temp.empty()) return 0 ;
  99.         return mod ;
  100.     }
  101.     if(dp.find({idx,temp}) != dp.end()) return dp[{idx,temp}] ;
  102.     int &res = dp[{idx,temp}] ;
  103.     vector<int> temp0 , temp1 ;
  104.     int j = 0 ;
  105.     while(j < temp.size() && forbid[temp[j]][idx] == '0') {
  106.         temp0.pb(temp[j]) ; ++j ;
  107.     }
  108.     while(j < temp.size() && forbid[temp[j]][idx] == '1') {
  109.         temp1.pb(temp[j]) ; ++j ;
  110.     }
  111.     res = solve(idx + 1 , temp0) + cnt[1][idx] ;
  112.     res = min(res , solve(idx + 1 , temp1) + cnt[0][idx]) ;
  113.     return res ;
  114. }
  115. int32_t main()
  116. {
  117.     fast;
  118.     #ifndef ONLINE_JUDGE
  119.     freopen("B.in","r",stdin) ;
  120.     freopen("output.txt","w",stdout) ;
  121.     #endif // ONLINE_JUDGE
  122.     int t ; cin >> t ;
  123.     rep(tt,1,t) {
  124.         cin >> n >> m >> p ;
  125.         rep(i,1,n) cin >> arr[i] ;
  126.         rep(i,1,m) cin >> forbid[i] ;
  127.         memset(cnt , 0 , sizeof(cnt)) ;
  128.         rep(pos,0,p-1) {
  129.             rep(j,0,1) {
  130.                 rep(i,1,n) {
  131.                     cnt[j][pos] += (arr[i][pos] == ('0' + j)) ;
  132.                 }
  133.             }
  134.         }
  135.         vector<pair<string,int> > bla ;
  136.         rep(i,1,m) bla.push_back({forbid[i],i}) ;
  137.         sort(all(bla)) ;
  138.         vector<int> temp ;
  139.         rep(i,0,m-1) temp.pb(bla[i].second) ;
  140.         int ans = solve(0,temp) ;
  141.         cout << "Case #" << tt << ": " << ans << endl ;
  142.         dp.clear() ;
  143.     }
  144.     return 0;
  145. }
  146.  
Success #stdin #stdout 0s 4512KB
comments (?)
stdin
copy 
2
3 1 4
1100
1010
0000
1000
2 4 4
1111
1111
1111
0111
1011
1101
stdout
copy 
Case #1: 4
Case #2: 2
https://ideone.com/HfxR4M
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!