Subscriptions#12285
Author of the problem: | Andrii Kholod (Connect) |
Prepared by: | Andrii Kholod (Connect) |
Analysis: | Andrii Kholod (Connect) |
Solution
Notice that since the first subscription can be purchased for any number of minutes, it is always beneficial to buy it last. Then we only need to iterate over all possible combinations of buying subscriptions 2, 3, and 4, and the remaining time will be covered by the first subscription.
The time complexity of the solution is O(1).
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
void solve() {
ll x1 , x2 , x3 , x4;
cin>>x1>>x2>>x3>>x4;
ll t2 , t3 , t4;
cin>>t2>>t3>>t4;
ll q;
cin>>q;
// use only 1;
ll res = q*x1;
// use 2;
ll curr = 0;
curr+=x2;
curr+=x1*max(0LL ,(q - t2));
res = min(curr , res);
// use 3;
curr = 0;
curr+=x3;
curr+=x1*max(0LL ,(q - t3));
res = min(curr , res);
// use 4;
curr = 0;
curr+=x4;
curr+=x1*max(0LL ,(q - t4));
res = min(curr , res);
// use 2, 3;
curr = 0;
curr+=x2+x3;
curr+=x1*max(0LL ,(q - t2 - t3));
res = min(curr , res);
// use 2, 4;
curr = 0;
curr+=x2+x4;
curr+=x1*max(0LL ,(q - t2 - t4));
res = min(curr , res);
// use 3, 4;
curr = 0;
curr+=x3+x4;
curr+=x1*max(0LL ,(q - t3 - t4));
res = min(curr , res);
// use 2, 3, 4;
curr = 0;
curr+=x2+x3+x4;
curr+=x1*max(0LL ,(q - t2 - t3 - t4));
res = min(curr , res);
cout<<res<<endl;
}
signed main() {
speed;
solve();
return 0;
}