fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long ll;
  4. using namespace std;
  5.  
  6. struct Counter
  7. {
  8. 	static int k;
  9. 	Counter() {k++;}
  10. 	~Counter() {k--;}
  11. };
  12.  
  13. int Counter::k = 0;
  14.  
  15. template<typename T>
  16. void pr(const string& name, T t)
  17. {
  18.     cout << name << " = " << t << endl;
  19. }
  20.  
  21. template<typename T, typename ... Types>
  22. void pr(const string& names, T t, Types ... rest)
  23. {
  24.     auto comma_pos = names.find(',');
  25.     cout << names.substr(0, comma_pos) << " = " << t << ", ";
  26.  
  27.     auto next_name_pos = names.find_first_not_of(" \t\n", comma_pos + 1);
  28.     pr(string(names, next_name_pos), rest ...);
  29. }
  30.  
  31. void mod(ll &a, ll b)
  32. {
  33.     a %= b;
  34.     if(a < 0) a += b;
  35. }
  36.  
  37. #define all(x) x.begin(), x.end()
  38. #define f(i,a,b) for(int i = (a); i <= (b); i++)
  39. #define fd(i,a,b) for(int i = (a); i >= (b); i--)
  40. #define mp make_pair
  41. #define faster_io() ios_base::sync_with_stdio(false)
  42. #define pb push_back
  43. #define pii pair<int,int>
  44. #define SZ(x) ((int)x.size())
  45. #define trace(...) pr(#__VA_ARGS__, __VA_ARGS__);
  46. #define tracea(x) {string s = #x; Counter c##x; cout<<s.substr(0,1+s.find('['))<<Counter::k<<"]="<<x<<'\n';}
  47. #define vii vector<pair<int,int>>
  48.  
  49. const ll MOD = 1000000007;
  50.  
  51. // ----------------------------------------------------------------------------------------------------------
  52.  
  53. ifstream fin("guard.in");
  54. ofstream fout("guard.out");
  55.  
  56. struct Cow
  57. {
  58.     ll h, w, str;
  59.     Cow(ll p1, ll p2, ll p3) : h(p1), w(p2), str(p3) {};
  60.     friend bool operator < (Cow c1, Cow c2)
  61.     {
  62.         return c1.str > c2.str;
  63.     }
  64. };
  65.  
  66. const ll INF = 1000000000000000000ll;
  67. ll N, J, Rem[1100000], H[1100000];
  68. vector<Cow> V;
  69.  
  70. int main()
  71. {
  72.     fin >> N >> J;
  73.  
  74.     f(i,1,N)
  75.     {
  76.         ll h, w, str;
  77.         fin >> h >> w >> str;
  78.         V.pb(Cow(h,w,str));
  79.     }
  80.  
  81.     ll ans = -1;
  82.     Rem[0] = INF;
  83.  
  84.     f(m,1,(1<<N)-1) Rem[m] = -INF;
  85.  
  86.     f(m,0,(1<<N)-1)
  87.     {
  88.         if(H[m] >= J) ans = max(ans, Rem[m]);
  89.         f(i,0,N-1) if(!(m&(1<<i)))
  90.         {
  91.             ll next_rem = min(Rem[m] - V[i].w, V[i].str);
  92.             ll next_h = H[m] + V[i].h;
  93.             ll next_mask = m + (1<<i);
  94.             H[next_mask] = next_h;
  95.             Rem[next_mask] = max(Rem[next_mask], next_rem);
  96.         }
  97.     }
  98.  
  99.     if(ans >= 0) fout << ans;
  100.     else fout << "Mark is too tall";
  101. }
  102.  
Success #stdin #stdout 0s 20616KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/q2AGwZ
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!