Abunəliklər#12285
Daxil ol

Abunəliklər (Həll təhlili)

Məsələnin müəllifi:

Andrey Xolod (Connect)

Hazırlayan:

Andrey Xolod (Connect)

Təhlil:

Andrey Xolod (Connect)

Həll

Qeyd edək ki, birinci abunəlik istənilən qədər dəqiqəlik alına bildiyi üçün onu həmişə sonda almaq sərfəlidir. Beləliklə, bizə yalnız 2, 3 və 4-cü abunəliklərin bütün kombinasiyalarını nəzərdən keçirmək qalır, qalan vaxt isə birinci abunəliklə örtüləcək.

Həllin asimptotik mürəkkəbliyi — 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;

    // yalnız 1-dən istifadə;

    ll res = q*x1;

    // 2-dən istifadə;

    ll curr = 0;

    curr+=x2;
    curr+=x1*max(0LL ,(q - t2));
    res = min(curr , res);

    // 3-dən istifadə;
    curr = 0;

    curr+=x3;
    curr+=x1*max(0LL ,(q - t3));
    res = min(curr , res);

    // 4-dən istifadə;
    curr = 0;

    curr+=x4;
    curr+=x1*max(0LL ,(q - t4));
    res = min(curr , res);

    // 2 və 3-dən istifadə;
    curr = 0;

    curr+=x2+x3;
    curr+=x1*max(0LL ,(q - t2 - t3));
    res = min(curr , res);

    // 2 və 4-dən istifadə;
    curr = 0;
        
    curr+=x2+x4;
    curr+=x1*max(0LL ,(q - t2 - t4));
    res = min(curr , res);

    // 3 və 4-dən istifadə;
    curr = 0;

    curr+=x3+x4;
    curr+=x1*max(0LL ,(q - t3 - t4));
    res = min(curr , res);

    // 2, 3 və 4-dən istifadə;
    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;
}
C++