734C - Anton and Making Potions - CodeForces Solution

binary search dp greedy two pointers *1600

Please click on ads to support us..

Python Code: 

import sys

n, m, k = map(int, input().split())

x, s = map(int, input().split())

a = [x] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

c = [0] + list(map(int, input().split()))
d = [0] + list(map(int, input().split()))

best = sys.maxsize ** 2 + 1

def search(left):
    l = 0
    r = k
    while l < r:
        m = (l + r + 1) // 2
        if d[m] <= left:
            l = m
        else:
            r = m-1
    return c[l]

for first_spell_i in range(m+1):
    ai = a[first_spell_i]
    bi = b[first_spell_i]
    left = s - bi
    if left < 0:
        continue

    cj = search(left)

        cost = ai * (n-cj)
    best = min(best, cost)

print(best)

C++ Code: 

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define Maxn 2000003

using namespace std;

typedef long long int LL;

LL n,m,k,x,s,x1,s1;

LL a_short_time[Maxn] = {0};
LL a_cost[Maxn] = {0};

LL b_pro_num[Maxn] = {0};
LL b_cost[Maxn] = {0};

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k>>x>>s;
    LL i = 1;
    LL ans = n*x;
    for(i = 1; i <= m; i++)
        cin >> a_short_time[i];
    a_short_time[0] = x;
    for(i = 1; i <= m; i++)
        cin >> a_cost[i];
    for(i = 1; i <= k; i++)
        cin >> b_pro_num[i];
    for(i = 1; i <= k; i++)
        cin >> b_cost[i];
    for(i = 0; i <= m; i++)
    {
        if(s >= a_cost[i])
        {
            LL s1 = s - a_cost[i];
            LL l = 0,r = k;
            while(l < r)
            {
                LL mid = (l + r) / 2;
                if(b_cost[mid] <= s1)
                {
                    if(b_cost[mid+1] > s1)
                    {
                        l = mid;
                        break;
                    }
                    else
                        l = mid + 1;
                }
                else
                    r = mid;
            }
            ans = min(ans,a_short_time[i]*(n-b_pro_num[l]));
        }
    }
    cout << ans;
    return 0;
}


Comments

Submit
0 Comments
More Questions

810B - Summer sell-off
84A - Toy Army
185A - Plant
1749A - Cowardly Rooks
1749C - Number Game
1749B - Death's Blessing
1749D - Counting Arrays
1447B - Numbers Box
1594D - The Number of Imposters
984B - Minesweeper
837A - Text Volume
1566C - MAX-MEX Cut
1546A - AquaMoon and Two Arrays
897B - Chtholly's request
1363B - Subsequence Hate
437B - The Child and Set
1256B - Minimize the Permutation
733B - Parade
172A - Phone Code
148D - Bag of mice
421A - Pasha and Hamsters
1393A - Rainbow Dash Fluttershy and Chess Coloring
980E - The Number Games
219B - Special Offer Super Price 999 Bourles
560B - Gerald is into Art
322B - Ciel and Flowers
801B - Valued Keys
975C - Valhalla Siege
518B - Tanya and Postcard
514B - Han Solo and Lazer Gun