Choosing a Bouquet
National Olympiad — National round
Submission name: bouquet.cpp
Problem summary
Choose exactly n flowers from m types, each available without limit. Taking x>0 flowers of type i contributes aᵢ+(x−1)bᵢ; choosing none contributes zero. Maximize the total contribution.
Input
n m, then m pairs aᵢ bᵢ.
Output
The maximum total contribution.
Constraints
1 ≤ n ≤ 10⁹; 1 ≤ m ≤ 100,000; 0 ≤ aᵢ,bᵢ ≤ 10⁹.
Worked example
An independently prepared example for this explanation.
Input
3 2 7 1 2 5
Output
14
Solution analysis
- An optimum can put all repeated flowers into a single chosen type: shift repeats to the chosen type with largest b. Enumerate that repeated type.
- Reserve its first flower, then select up to n−1 other first flowers with a>b for this type. Sorted first-flower values and prefix sums evaluate this choice by binary search, excluding the reserved type if present. Fill remaining positions with repeats. Also consider choosing n distinct types.
Why it works
For fixed chosen types, moving repeats to the largest repeat reward cannot hurt. For a fixed repeated type, each additional first flower replaces one repeat and is useful exactly when its reward is larger. Taking the largest such rewards is optimal, and enumerating the repeated type covers every optimum.
Watch out. The first flower of the repeated type is mandatory, even when aᵢ<bᵢ. Use 64-bit totals.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
#include<functional>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
int m;
cin>>n>>m;
vector<pair<long long,long long>>a(m);
vector<long long>s(m);
for(int i=0;i<m;i++){
cin>>a[i].first>>a[i].second;
s[i]=a[i].first;
}
sort(s.rbegin(),s.rend());
vector<long long>p(m+1);
for(int i=0;i<m;i++){
p[i+1]=p[i]+s[i];
}
long long ans=n<=m?p[n]:0;
for(auto[x,b]:a){
int count=lower_bound(s.begin(),s.end(),b,greater<long long>())-s.begin();
long long take=min<long long>(n-1,count-(x>b));
long long sum=p[take];
// Remove this type's reserved first flower from the chosen largest rewards.
if(x>b&&take>0&&x>=s[take-1]){
sum=p[take+1]-x;
}
ans=max(ans,x+sum+(n-1-take)*b);
}
cout<<ans<<'\n';
}