Codeforces Round #834 (Div. 3) E. The Humanoid

Let’s make two obvious remarks:

If we can absorb two astronauts with power x≤yx≤yx≤y, then we can always first absorb an astronaut with power xxx, and then an astronaut with power yyy;If we can absorb some astronaut, it is effective for us to do it right now.

Let’s sort the astronauts powers in increasing order.

Now let’s lock the sequence of serums we use. There are only three of them: blue serum can be the first, second or third.

Let’s absorb the astronauts in increasing order of their powers, and if we can’t, then use the next serum in a locked sequence or stop.

This solution works for O(n)O(n)O(n).

#include<bits/stdc++.h>using namespace std;int main(){int T;cin>>T;while(T--){int n,h;cin>>n>>h;vector<int> a(n);for(int i=0;i<n;i++) cin>>a[i];sort(a.begin(),a.end());vector<int> b{2,2,3};int mx=0;do{long long res=h;int pos=0;for(int i=0,j=0;i<n;){if(res>a[i]) res+=a[i++]/2;else if(j<3) res*=b[j++];else break;pos=i;}mx=max(mx,pos);}while(next_permutation(b.begin(),b.end()));cout<<mx<<endl;}return 0;}