1793E - Velepin and Marketing - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); 
	
	int T;
	T = 1;
	while(T--){
		int n;
		cin >> n;
		vector<int> a(n);
		for(int i = 0; i < n; ++i){
			cin >> a[i];
		}
		sort(a.begin(), a.end());
		vector<int> f(n + 1, -1e9);
		vector<int> ans(n + 1);
		
		f[0] = 0;
		for(int i = 1; i <= n; ++i){
			if(i >= a[i - 1]){
				f[i] = f[i - a[i - 1]] + 1;
				ans[f[i] + n - i] = max(ans[f[i] + n - i], i);
			}else{
				ans[n - a[i - 1] + 1] = max(ans[n - a[i - 1] + 1], i);
			}
			f[i] = max(f[i], f[i - 1]);
		} 
		
		for(int i = n - 1; i >= 2; --i){
			ans[i] = max(ans[i], ans[i + 1]);
		}
		
		int q;
		cin >> q;
		while(q--){
			int k;
			cin >> k;
			cout << ans[k] << '\n';
		}
		
	}
}