PROBLEM LINK:
Setter: Hasan Jaddouh
Tester: Teja Vardhan Reddy
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
PREREQUISITES:
Greedy
PROBLEM:
There are M flavours of drinks each of C_i cups. They are N people entering the store in that order. Each person has a favourite drink. If his favourite flavour is available in the store, he pays F_i and buys one cups of it otherwise pays B_i and accepts any flavour of one cup (chef can choose this flavour). Now we want to maximise the profit.
QUICK EXPLANATION
- We assign a person’s favourite flavour if its present. Otherwise we assign to him later one of flavours left behind after assigning favourite flavours for others.
EXPLANATION
Claim: If a person’s(lets say p_1) favourite flavour is not present, its always optimal to give that person a flavour (lets say x) such that no other person misses that flavour later with it as their favourite flavour.
Proof:
Lets says p_2 was the first person who missed flavour x with flavour x as his favourite flavour. Now let the total profit was G. Now lets say p_2 was given flavour y since x was not available. Now, if we had given p_1 flavour y then x would have been available for p_2 with rest being same so we would have given x to p_2. In such a scenario, total profit is G + F[p_2]-B[p_2]) (\gt G). Hence, proved.
Now, the above one proves that we want to maximise people getting their favourite flavours. So if a person’s favourite flavour is not present, lets not assign him a flavour immediately. We will assign him one of the flavours left over at the end. Then, nobody would have missed favourite flavour because of him.
TIME COMPLEXITY
O(n+m).
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
if(!(l<=x && x<=r)){
cerr<<l<<" "<<r<<" "<<x<<endl;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n,m;
int C[100100];
int D[100100];
int B[100100];
int F[100100];
int ans[100100];
int sm_n=0;
int sm_m=0;
int main(){
//freopen("03.txt","r",stdin);
//freopen("03o.txt","w",stdout);
T=readIntLn(1,1000);
while(T--){
n=readIntSp(2,100000);
m=readIntLn(2,100000);
sm_n += n;
sm_m += m;
assert(sm_n <= 1000000);
assert(sm_m <= 1000000);
long long sm_c=0;
for(int i=1;i<=m;i++){
if(i==m){
C[i]=readIntLn(1,n);
} else {
C[i]=readIntSp(1,n);
}
sm_c += C[i];
}
assert(sm_c >= n);
long long sol = 0;
for(int i=1;i<=n;i++){
D[i]=readIntSp(1,m);
F[i]=readIntSp(2,1000000000);
B[i]=readIntLn(1,F[i]-1);
if(C[D[i]] > 0){
sol += F[i];
ans[i] = D[i];
C[D[i]]--;
} else {
sol += B[i];
ans[i] = -1;
}
}
int cur = 1;
for(int i=1;i<=n;i++){
if(ans[i]!=-1)continue;
while(C[cur] == 0)cur++;
ans[i] = cur;
C[cur] --;
}
cout<<sol<<endl;
for(int i=1;i<=n;i++){
if(i==n){
cout<<ans[i]<<endl;
} else{
cout<<ans[i]<<" ";
}
}
}
assert(getchar()==-1);
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int c[123456],d[123456],b[123456],f[123456],happy[123456];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
int i;
rep(i,m){
cin>>c[i];
}
rep(i,n){
cin>>d[i]>>f[i]>>b[i];
d[i]--;
}
ll ans=0;
rep(i,n){
happy[i]=0;
if(c[d[i]]){
c[d[i]]--;
happy[i]=1;
ans+=f[i];
}
else
ans+=b[i];
}
int j=0;
cout<<ans<<endl;
rep(i,n){
if(happy[i]){
cout<<d[i]+1<<" ";
continue;
}
while(c[j]==0)
j++;
cout<<j+1<<" ";
c[j]--;
}
cout<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
Ill do some more debugging and if no result then I’ll ask for help here 
