#include #include #include #include #include // Required for std::min // Function to check if k thousand yen can be paid with current available bills. // It attempts to find a valid combination of bills (pay_x, pay_y, pay_z) such that // pay_x * 1 + pay_y * 5 + pay_z * 10 = k thousand yen, // and pay_x <= current_x, pay_y <= current_y, pay_z <= current_z. // The function uses a primary greedy strategy (largest denominations first). // If the primary strategy fails due to insufficient 1000 yen bills, it attempts // an alternative strategy: using one fewer 10000 yen bill (if possible) and // compensating with 5000 and 1000 yen bills. // If a valid combination is found, it returns true and outputs the combination via reference parameters. // Otherwise, it returns false. bool can_pay(long long k, long long current_x, long long current_y, long long current_z, long long& used_x, long long& used_y, long long& used_z) { // Basic check: cannot pay non-positive amounts. if (k <= 0) return false; // Try standard greedy approach (largest denominations first) long long k_rem = k; // k is the target amount in thousands of yen // Calculate the number of 10000 yen bills to use greedily // Use at most current_z bills, and at most floor(k_rem / 10) bills. long long greedy_z = std::min(current_z, k_rem / 10); k_rem -= greedy_z * 10; // Subtract the value covered by 10k bills // Calculate the number of 5000 yen bills to use greedily // Use at most current_y bills, and at most floor(k_rem / 5) bills. long long greedy_y = std::min(current_y, k_rem / 5); k_rem -= greedy_y * 5; // Subtract the value covered by 5k bills // The remaining amount must be covered by 1000 yen bills long long greedy_x = k_rem; // Check if the greedy combination is possible (i.e., have enough 1000 yen bills) if (greedy_x <= current_x) { // Greedy combination works. Set the output parameters and return true. used_x = greedy_x; used_y = greedy_y; used_z = greedy_z; return true; } // If the greedy approach failed because we needed too many 1000 yen bills (greedy_x > current_x) // Check an alternative strategy: using one fewer 10000 yen bill. // This is only possible if the greedy approach attempted to use at least one 10000 yen bill (greedy_z >= 1). if (greedy_z >= 1) { // Try using one fewer 10k bill long long alt_z = greedy_z - 1; // Recalculate the remaining amount to cover with 5k and 1k bills. // The new remaining amount is k - alt_z * 10 = k - (greedy_z - 1) * 10 = (k - greedy_z * 10) + 10 // This is the remainder from the first step of greedy + 10. long long k_rem_alt = k - alt_z * 10; // Cover k_rem_alt using 5k and 1k bills, again greedily long long alt_y = std::min(current_y, k_rem_alt / 5); k_rem_alt -= alt_y * 5; long long alt_x = k_rem_alt; // Remainder must be covered by 1k bills // Check if this alternative combination is valid: requires enough 1k and 5k bills. // We already know alt_z is valid because alt_z < greedy_z <= current_z. if (alt_x <= current_x && alt_y <= current_y) { // Alternative combination works. Set output parameters and return true. used_x = alt_x; used_y = alt_y; used_z = alt_z; return true; } } // If both the standard greedy strategy and the alternative strategy (if applicable) failed return false; } int main() { // Use faster I/O operations std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int N; // Number of shops long long X, Y, Z; // Initial counts of 1000, 5000, 10000 yen bills std::cin >> N >> X >> Y >> Z; std::vector A(N); // Costs at each shop for (int i = 0; i < N; ++i) { std::cin >> A[i]; } // Current available bills long long current_x = X; long long current_y = Y; long long current_z = Z; // Process purchases for each shop sequentially for (int i = 0; i < N; ++i) { long long k_min; // Minimum required payment amount in thousands of yen // Calculate k_min based on the cost A[i] if (A[i] % 1000 == 0) { // If A[i] is exactly a multiple of 1000, Yuki must pay strictly more. // The minimum payment is A[i] + 1000 yen. k_min = A[i] / 1000 + 1; } else { // If A[i] is not a multiple of 1000, Yuki must pay at least the next multiple of 1000. // This is ceil(A[i] / 1000.0) thousands of yen. // Using integer division: (A[i] + 999) / 1000 k_min = (A[i] + 999) / 1000; } bool paid = false; // Flag to track if payment was successful for the current shop long long k_to_pay = -1; // The actual amount paid (in thousands) long long pay_x = 0, pay_y = 0, pay_z = 0; // Bills used for the payment // Try to find the smallest payable amount k >= k_min. // We check a small range starting from k_min. Based on analysis, checking up to // k_min + 9 seems sufficient to cover cases where paying slightly more than // the minimum required amount becomes possible due to bill combinations. for (long long k = k_min; k <= k_min + 9; ++k) { // Check if 'k' thousand yen can be paid using current bills. // Pass temporary variables to receive the used bill counts if payment is possible. long long temp_used_x, temp_used_y, temp_used_z; if (can_pay(k, current_x, current_y, current_z, temp_used_x, temp_used_y, temp_used_z)) { // Found the smallest k >= k_min that is payable. k_to_pay = k; // Store the bill combination used for this payment. pay_x = temp_used_x; pay_y = temp_used_y; pay_z = temp_used_z; paid = true; // Mark payment as successful break; // Stop searching, as we want the minimum possible payment } } if (paid) { // Payment was successful for shop i. Update the available bill counts. current_x -= pay_x; current_y -= pay_y; current_z -= pay_z; } else { // If no payable amount k was found in the checked range [k_min, k_min + 9] // Yuki cannot make this purchase according to the rules. std::cout << "No" << std::endl; return 0; // Exit program indicating failure } } // If the loop completes, all N purchases were successfully made. std::cout << "Yes" << std::endl; return 0; }