You eat snacks every day for n days.
On day i you must eat exactly dᵢ snacks, and that day the shop sells as many snacks as you like at pᵢ each.
On a day you buy snacks you have to go to the shop, which costs a fare of f once that day, however many you buy.
On a day you buy no snacks you do not go to the shop, so there is no fare.
A snack can be eaten the day it is bought, or kept in the fridge and eaten on a later day.
Each day goes in this order: buy, eat, put in the fridge.
All snacks left after eating must go into the fridge that night, and the fridge holds at most C snacks.
Each snack in the fridge costs h per night to keep.
On the morning of the first day you have no snacks.
If snacks are left on the last night, they also go into the fridge and you pay for keeping them.
Print the smallest amount of money (snack prices, fares and keeping costs together) with which you eat the required number of snacks on all n days.
Input
The first line has n, C, h and f, the second line p₁ … pₙ, and the third line d₁ … dₙ, separated by spaces. 1 ≤ n ≤ 500, 0 ≤ C ≤ 500, 0 ≤ h ≤ 1,000,000, 0 ≤ f ≤ 1,000,000,000, 1 ≤ pᵢ ≤ 1,000,000, 0 ≤ dᵢ ≤ 1,000
Output
One number, the smallest amount of money
Example 1 · stdin
4 3 1 8
2 9 9 3
2 2 2 1
stdout
49
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The state is 'the number s left in the fridge that night' (0 to C): best[s] = the least money spent to get there. With s in the morning, buying b, eating d and keeping s2 that night means b = s2 + d − s, and there are two ways. Not going to the shop means b = 0, so s can only be s2 + d (only when s2 + d ≤ C), and the money is best[s2 + d] + s2·h. Going to the shop costs min(best[s] − s·p) + (s2 + d)·p + f + s2·h, with the min over s where s ≤ s2 + d (s = s2 + d would mean paying the fare without buying, which is always dearer than the first way, so including it does no harm). Trying every s is C² = 250,000 per day, 125 million for 500 days, too slow for Python and Craykon. As s2 grows from 0 the allowed range of s only grows, so build the minimum up from the front (low) and finish a day in C steps. The answer is best[0] — leaving snacks on the last night only costs more. Example: on day 1 buy 5 at 2 (10 + fare 8), eat 2 and keep 3 (a full fridge) (3); on day 2 skip the shop, eat 2 and keep 1 (1); on day 3 buy 2 at 9 (18 + 8), eat 2 and keep 1 (1); on day 4 skip the shop — 49. Day 4's price of 3 is cheaper, but buying one more at 9 on day 3 saves the fare of 8. Trap one: forgetting the fare gives 26 — the common solution with only a fridge limit and keeping costs is not enough. Trap two: the opposite, paying the fare every day (even on days you buy nothing), is wrong too — the way of not going to the shop must be handled separately. Trap three: buying each day's snacks that day with no fridge, or the greedy 'always buy at the cheapest price so far plus keeping', cannot account for the fridge limit and the fare, so they are wrong — you must choose which days' snacks to buy early, which needs DP. Trap four: forgetting the keeping cost, or checking the limit before eating (s2 + d ≤ C), is wrong — the snacks eaten that day never go into the fridge. Trap five: the money can reach fares 500 × 1,000,000,000 + snacks 500 × 1,000 × 1,000,000 + keeping 500 × 500 × 1,000,000 ≈ 1.25×10^12, past a 32-bit int (about 2.1 billion). C and C++ need long long, Java and C# long; Python integers have no limit, and JavaScript, TypeScript and Craykon numbers are doubles, exact up to 2^53 (about 9×10^15), so they work as they are. The value meaning 'not possible yet' differs too: Python float("inf"), JavaScript and TypeScript Infinity (Infinity − x is still Infinity); Java, C#, C and C++ use a large number that cannot overflow when added to or subtracted from (such as Long.MAX_VALUE / 4) and filter with a comparison — adding to MAX_VALUE itself overflows into a negative number. Craykon has no infinity, so it uses -1 for 'not possible' and null for 'no minimum yet' (calculating with null stops the program, so ask first, as in low == null || …).
Pythonmain.py · 31 lines
import sysdata = sys.stdin.read().split()n, cap, keep, fare = int(data[0]), int(data[1]), int(data[2]), int(data[3])price = [int(x) for x in data[4 : 4 + n]]eat = [int(x) for x in data[4 + n : 4 + 2 * n]]INF = float("inf")# best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈best = [0] + [INF] * capfor day in range(n): p, d = price[day], eat[day] # 오늘 아침 s개가 있고, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s # 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep # 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d) # 그래서 s <= s2 + d인 s 가운데 (best[s] - s * p)가 가장 작은 것만 알면 된다: s2를 늘리며 앞에서부터 최솟값을 쌓는다 new = [INF] * (cap + 1) low = INF # s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 s = 0 for s2 in range(cap + 1): while s <= cap and s <= s2 + d: if best[s] != INF: low = min(low, best[s] - s * p) s += 1 if low != INF: new[s2] = low + (s2 + d) * p + fare + s2 * keep if s2 + d <= cap: # 가게에 가지 않는 날: 차비가 없다 new[s2] = min(new[s2], best[s2 + d] + s2 * keep) best = new# 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다print(best[0])
JavaScriptmain.js · 30 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, cap, keep, fare] = data;const price = data.slice(4, 4 + n);const eat = data.slice(4 + n, 4 + 2 * n);// best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 number로 정확하다)let best = new Array(cap + 1).fill(Infinity);best[0] = 0;for (let day = 0; day < n; day++) { const p = price[day], d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 const next = new Array(cap + 1).fill(Infinity); let low = Infinity; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 let s = 0; for (let s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { low = Math.min(low, best[s] - s * p); // Infinity - 수 = Infinity라 따로 거르지 않아도 된다 s++; } next[s2] = low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = Math.min(next[s2], best[s2 + d] + s2 * keep); } } best = next;}// 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다console.log(best[0]);
TypeScriptmain.ts · 32 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, cap, keep, fare] = data;const price: number[] = data.slice(4, 4 + n);const eat: number[] = data.slice(4 + n, 4 + 2 * n);// best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 number로 정확하다)let best: number[] = new Array<number>(cap + 1).fill(Infinity);best[0] = 0;for (let day = 0; day < n; day++) { const p = price[day], d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 const next: number[] = new Array<number>(cap + 1).fill(Infinity); let low = Infinity; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 let s = 0; for (let s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { low = Math.min(low, best[s] - s * p); // Infinity - 수 = Infinity라 따로 거르지 않아도 된다 s++; } next[s2] = low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = Math.min(next[s2], best[s2 + d] + s2 * keep); } } best = next;}// 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다console.log(best[0]);
JavaMain.java · 51 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int cap = Integer.parseInt(st.nextToken()); long keep = Long.parseLong(st.nextToken()); long fare = Long.parseLong(st.nextToken()); long[] price = new long[n]; int[] eat = new int[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) price[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) eat[i] = Integer.parseInt(st.nextToken()); final long INF = Long.MAX_VALUE / 4; // 더하거나 빼도 넘치지 않을 만큼 큰 수 // best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long) long[] best = new long[cap + 1]; Arrays.fill(best, INF); best[0] = 0; for (int day = 0; day < n; day++) { long p = price[day]; int d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 long[] next = new long[cap + 1]; long low = INF; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF) low = Math.min(low, best[s] - s * p); s++; } next[s2] = low == INF ? INF : low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap && best[s2 + d] < INF) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = Math.min(next[s2], best[s2 + d] + s2 * keep); } } best = next; } // 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 System.out.println(best[0]); }}
C#Main.cs · 48 lines
using System;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); int cap = int.Parse(first[1]); long keep = long.Parse(first[2]); long fare = long.Parse(first[3]); long[] price = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); int[] eat = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse); const long INF = long.MaxValue / 4; // 더하거나 빼도 넘치지 않을 만큼 큰 수 // best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long) var best = new long[cap + 1]; Array.Fill(best, INF); best[0] = 0; for (int day = 0; day < n; day++) { long p = price[day]; int d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 var next = new long[cap + 1]; long low = INF; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF) low = Math.Min(low, best[s] - s * p); s++; } next[s2] = low == INF ? INF : low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap && best[s2 + d] < INF) // 가게에 가지 않는 날: 차비가 없다 { next[s2] = Math.Min(next[s2], best[s2 + d] + s2 * keep); } } best = next; } // 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 Console.WriteLine(best[0]); }}
C++main.cpp · 45 lines
#include <algorithm>#include <iostream>#include <limits>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, cap; long long keep, fare; std::cin >> n >> cap >> keep >> fare; std::vector<long long> price(n); std::vector<int> eat(n); for (auto& p : price) std::cin >> p; for (auto& d : eat) std::cin >> d; const long long INF = std::numeric_limits<long long>::max() / 4; // 더하거나 빼도 넘치지 않을 만큼 큰 수 // best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long long) std::vector<long long> best(cap + 1, INF); best[0] = 0; for (int day = 0; day < n; day++) { long long p = price[day]; int d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 std::vector<long long> next(cap + 1, INF); long long low = INF; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF) low = std::min(low, best[s] - s * p); s++; } if (low < INF) next[s2] = low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap && best[s2 + d] < INF) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = std::min(next[s2], best[s2 + d] + s2 * keep); } } best = std::move(next); } // 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 std::cout << best[0] << '\n'; return 0;}
Cmain.c · 45 lines
#include <stdio.h>#include <string.h>#define MAXN 500#define MAXC 500#define INF 1000000000000000000LL /* 더하거나 빼도 넘치지 않을 만큼 큰 수 */static long long price[MAXN];static int eat[MAXN];/* best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long long) */static long long best[MAXC + 1], next[MAXC + 1];int main(void) { int n, cap; long long keep, fare; if (scanf("%d %d %lld %lld", &n, &cap, &keep, &fare) != 4) return 0; for (int i = 0; i < n; i++) scanf("%lld", &price[i]); for (int i = 0; i < n; i++) scanf("%d", &eat[i]); for (int s = 0; s <= cap; s++) best[s] = INF; best[0] = 0; for (int day = 0; day < n; day++) { long long p = price[day]; int d = eat[day]; /* 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 */ long long low = INF; /* s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 */ int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF && best[s] - s * p < low) low = best[s] - s * p; s++; } next[s2] = low < INF ? low + (s2 + d) * p + fare + s2 * keep : INF; if (s2 + d <= cap && best[s2 + d] < INF && best[s2 + d] + s2 * keep < next[s2]) { next[s2] = best[s2 + d] + s2 * keep; /* 가게에 가지 않는 날: 차비가 없다 */ } } memcpy(best, next, sizeof(long long) * (cap + 1)); } /* 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 */ printf("%lld\n", best[0]); return 0;}
Craykonmain.cray · 45 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];cap = 첫줄[1];keep = 첫줄[2];fare = 첫줄[3];price = Console.ReadNumbers();eat = Console.ReadNumbers();// best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(-1은 아직 그렇게 될 수 없음)best = NewList(cap + 1, -1);best[0] = 0;for (day = 0; day < n; day++){ p = price[day]; d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 next = NewList(cap + 1, -1); low = null; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값(빈값은 아직 없음) s = 0; for (s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] != -1 && (low == null || best[s] - s * p < low)) { low = best[s] - s * p; } s++; } if (low != null) { next[s2] = low + (s2 + d) * p + fare + s2 * keep; } // 가게에 가지 않는 날: 차비가 없다 if (s2 + d <= cap && best[s2 + d] != -1 && (next[s2] == -1 || best[s2 + d] + s2 * keep < next[s2])) { next[s2] = best[s2 + d] + s2 * keep; } } best = next;}// 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다Console.WriteLine(best[0]);