fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <utility>
  10. #include <cstdlib>
  11. #include <memory>
  12. #include <queue>
  13. #include <cassert>
  14. #include <cmath>
  15. #include <ctime>
  16. #include <complex>
  17. #include <bitset>
  18.  
  19. using namespace std;
  20.  
  21. #define pb push_back
  22. #define fst first
  23. #define snd second
  24. #define mp make_pair 
  25. #define sz(C) ((int) (C).size())
  26. #define forn(i, n) for (int i = 0; i < (int) n; ++i)
  27. #define ford(i, n) for (int i = ((int) n) - 1; i >= 0; --i)
  28. #define y1 gftxdtrtfhyjfctrxujkvbhyjice
  29. #define y0 ehfoiuvhefroerferjhfjkehfjke
  30. #define left sdhfsjkshdjkfsdfgkqqweqweh
  31. #define right yytrwtretywretwreytwreytwr
  32. #define next jskdfksdhfjkdsjksdjkgf
  33. #define prev koeuigrihjdkjdfj
  34. #define hash kjfdkljkdhgjdkfhgurehg
  35. #define all(C) begin(C), end(C)
  36.  
  37. typedef long long ll;
  38. typedef unsigned long long ull;
  39. typedef unsigned int uint;
  40. typedef pair <int,int> pii;
  41. typedef pair <ll, ll> pll;
  42. typedef vector <ll> vll;
  43. typedef vector <int> vi;
  44. typedef vector <vector <int> > vvi;
  45. typedef vector <pii> vii;
  46. typedef long double ld;
  47. typedef complex<double> cd;
  48. typedef vector<cd> vcd;
  49.  
  50. #define FILE_NAME ""
  51.  
  52. const ld EPS = 1e-9;
  53. const int MAXN = 50 + 5;
  54. const int MAXM = 1000 + 5;
  55.  
  56. char g[MAXN][MAXM];
  57. string name[MAXN];
  58. int n, m;
  59. int p[MAXN];
  60.  
  61. void read() {
  62.   scanf("%d%d", &n, &m);
  63.   forn(i, n) {
  64.     scanf("%d", &p[i]);
  65.   } 
  66.   scanf("\n");
  67.   forn(i, n) {
  68.     getline(cin, name[i]);
  69.   }
  70.   scanf("\n");
  71.   forn(i, n) {
  72.     scanf("%s", g[i]);
  73.   }
  74. }
  75.  
  76. string name1, name2, name3;
  77. int ans;
  78.  
  79.  
  80. int main() {
  81. #ifdef LOCAL
  82.   freopen(FILE_NAME ".in", "r", stdin);
  83. //  freopen(FILE_NAME ".out", "w", stdout);
  84. #endif
  85.  
  86.   read();
  87.  
  88.   ans = -1;
  89.   forn(i, n) for (int j = i + 1; j < n; ++j) for (int k = j + 1; k < n; ++k) {
  90.     vvi cnt(3, vi(3, 0));
  91.     int cnt_all = 0;
  92.     vi cnt_one(3, 0);
  93.     forn(z, m) {
  94.       int mask = 0;
  95.       if  (g[i][z] == '1') mask |= 1 << 0;
  96.       if  (g[j][z] == '1') mask |= 1 << 1;
  97.       if  (g[k][z] == '1') mask |= 1 << 2;
  98.       if  (!mask) {
  99.         continue;
  100.       }
  101.       int pop = __builtin_popcount(mask);
  102.       if  (pop == 1) {
  103.         forn(w, 3) {
  104.           if  (mask & (1 << w)) {
  105.             ++cnt_one[w];
  106.             break;
  107.           }
  108.         }
  109.       }
  110.       if  (pop == 3) {
  111.         ++cnt_all;
  112.       }
  113.       if  (pop == 2) {
  114.         int w1 = 0;
  115.         forn(w, 3) {
  116.           if  (mask & (1 << w)) {
  117.             w1 = w;
  118.             break;
  119.           }
  120.         }
  121.         int w2 = 0;
  122.         ford(w, 3) {
  123.           if  (mask & (1 << w)) {
  124.             w2 = w;
  125.             break;
  126.           }
  127.         }
  128.         assert(w1 < w2);
  129.         ++cnt[w1][w2];
  130.       }
  131.     }
  132.  
  133.     int cur = 0;
  134.     vi can(3, 0);
  135.     can[0] = p[i];
  136.     can[1] = p[j];
  137.     can[2] = p[k];
  138.     forn(w1, 3) forn(w2, 3) printf("cnt[%d][%d] = %d\n", w1, w2, cnt[w1][w2]);
  139.     forn(w, 3) {
  140.       while (cnt_one[w] > 0 && can[w] > 0) {
  141.         ++cur;
  142.         --cnt_one[w];
  143.         --can[w];
  144.       } 
  145.     }
  146.  
  147.     forn(w, 3) {
  148.       forn(w2, 3) {
  149.         if  (w == w2) {
  150.           continue;
  151.         }
  152.         while  (cnt[min(w, w2)][max(w, w2)] > can[w2] && can[w] > 0) {
  153.           --cnt[min(w, w2)][max(w, w2)];
  154.           --can[w];
  155.           ++cur;
  156. //          printf("w = %d\n", w);
  157.         }
  158.       }
  159.     }
  160.  
  161.     forn(w, 3) forn(w2, 3) {
  162.       if  (w != w2) {
  163.         while (cnt[min(w, w2)][max(w, w2)] > 0 && can[w] > 0) {
  164.           --can[w];
  165.           --cnt[min(w, w2)][max(w, w2)];
  166.           ++cur;
  167. //          printf("w = %d\n", w);
  168.         }
  169.       }
  170.     }
  171.  
  172.     forn(w, 3) {
  173.       while (cnt_all > 0 && can[w] > 0) {
  174.         --cnt_all;
  175.         --can[w];
  176.         ++cur;
  177.       }
  178.     }
  179.  
  180.     if  (cur > ans) {
  181.       ans = cur;
  182.       name1 = name[i];
  183.       name2 = name[j];
  184.       name3 = name[k];
  185.     }
  186.   }
  187.  
  188.   cout << ans << endl << name1 << " " << name2 << " " << name3 << endl;
  189.   return 0;
  190. }
  191.  
Success #stdin #stdout 0s 3288KB
comments (?)
stdin
copy 
3 6
4 1 1
Denis
Andrew
Egor
110011
111100
001111
stdout
copy 
cnt[0][0] = 0
cnt[0][1] = 2
cnt[0][2] = 2
cnt[1][0] = 0
cnt[1][1] = 0
cnt[1][2] = 2
cnt[2][0] = 0
cnt[2][1] = 0
cnt[2][2] = 0
6
Denis Andrew Egor
https://ideone.com/G2HgCg
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!