Source Code
#include <bits/stdc++.h>
using namespace std;
#define oo 1000000010
#define mod 1000000007
const int N = 300010;

vector< int > arr[3];

vector< long long > sum[3];

int n ,a , b , v;

inline long long getSum(int i,int l,int r){
	return sum[i][r + 1] - sum[i][l];
}

int main(){
	scanf("%d%d%d",&n,&a,&b);
	char k;
	for(int i = 0 ;i < n;i++){
		scanf(" %c%d",&k,&v);
		if(k == 's')
			arr[0].push_back(v);
		else if(k == 'c')
			arr[1].push_back(v);
		else
			arr[2].push_back(v);
	}
	for(int i = 0 ;i < 3;i++){
		sort(arr[i].begin(),arr[i].end());
		sum[i].push_back(0);
		for(int j = 0 ;j < (int)arr[i].size();j++){
			sum[i].push_back(sum[i].back() + arr[i][j]);
		}
	}


	int low , high , res , mid;
	int bad , good , start , take , tc , ts , rc , rs , rt , needed;

	long long ans = 0 , cur = 0;

	for(int i = 0 ;i <= (int)arr[2].size();i++){
		start = (b - (i % b)) % b;
		low = 0 , high = ((int)arr[1].size() / b) + 1 , res = -1;
		while(high >= low){
			mid = (low + high) / 2;
			take = start + mid * b;



			if(take > (int)arr[1].size()){
				high = mid - 1;
				continue;
			}



			bad = (i + take) / b;
			good = ((int)arr[1].size() - take + (int)arr[0].size()) / a;



			if(good < bad){
				high = mid - 1;
				continue;
			}
			good = bad;

			tc = min((int)arr[1].size() - take , good * a);
			ts = good * a - tc;


			rt = (int)arr[2].size() - i;
			rs = (int)arr[0].size()- ts;
			rc = (int)arr[1].size() - take - tc;


			needed = max(0 , a - rs) + max(0 , b - rt);


			if(rc >= needed)
				low = mid + 1;
			else{
				res = take;
				high = mid - 1;
			}

		}
		if(res == -1) continue;
		cur = sum[0].back() + getSum(2 , i , (int)arr[2].size() - 1) + getSum(1 , res , (int)arr[1].size() - 1);
		ans = max(ans , cur);
	}
	cout << ans << endl;
	return 0;
}
Copy
ClearTheBit Kilani
GNU G++17
190 ms
19.1 MB
Accepted