aboutsummaryrefslogtreecommitdiff
path: root/Practical2/checkout.c
diff options
context:
space:
mode:
Diffstat (limited to 'Practical2/checkout.c')
-rw-r--r--Practical2/checkout.c58
1 files changed, 28 insertions, 30 deletions
diff --git a/Practical2/checkout.c b/Practical2/checkout.c
index 289a50d..88d962e 100644
--- a/Practical2/checkout.c
+++ b/Practical2/checkout.c
@@ -1,6 +1,8 @@
#include <stdio.h>
#include <stdint.h>
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wreturn-type"
int8_t round_profit(uint32_t value) {
switch (value % 5) {
case 0: return 0;
@@ -10,61 +12,57 @@ int8_t round_profit(uint32_t value) {
case 4: return -1;
}
}
+#pragma GCC diagnostic pop
-int32_t maximum_profit(uint16_t products[], uint16_t n_products, uint8_t dividers) {
- int8_t profit[n_products+1][dividers+1];
- uint16_t p, d;
- for (p = 0; p <= n_products; p++) {
- uint32_t sums[p];
+int32_t maximum_profit(int seq[], uint16_t seq_len, uint8_t k) {
+ int8_t gain[seq_len+1][k+1];
+ uint16_t p, d, i;
+ for (p = 0; p <= seq_len; p++) {
+ uint32_t sum[p];
if (p == 0) {
- sums[0] = 0;
+ sum[0] = 0;
} else {
- sums[p-1] = products[p-1];
- int16_t i;
- for (i = p-2; i >= 0; i--) {
- sums[i] = products[i] + sums[i+1];
- }
+ sum[p-1] = seq[p-1];
+ for (i = p-2; i != UINT16_MAX; i--)
+ sum[i] = seq[i] + sum[i+1];
}
- for (d = 0; d <= dividers; d++) {
+ for (d = 0; d <= k; d++) {
if (p == 0) {
- profit[p][d] = 0;
+ gain[p][d] = 0;
} else if (d == 0) {
- profit[p][d] = round_profit(sums[0]);
+ gain[p][d] = round_profit(sum[0]);
} else {
- int8_t max = profit[p][d-1];
- uint16_t i;
+ int8_t max = gain[p][d-1];
for (i = 0; i < p; i++) {
- int8_t try = profit[i][d-1] + round_profit(sums[i]);
+ int8_t try = gain[i][d-1] + round_profit(sum[i]);
if (try > max)
max = try;
}
- profit[p][d] = max;
+ gain[p][d] = max;
}
}
}
- return profit[n_products][dividers];
+ return gain[seq_len][k];
}
int main(void) {
- int n_products;
- int dividers;
+ int seq_len, k;
uint32_t sum = 0;
+ scanf("%d %d", &seq_len, &k);
+ int seq[seq_len];
- scanf("%d %d", &n_products, &dividers);
-
- uint16_t products[n_products];
uint16_t i;
- for (i = 0; i < n_products; i++) {
- scanf("%d", &(products[i]));
- sum += products[i];
- if (products[i] % 5 == 0) {
- n_products--;
+ for (i = 0; i < seq_len; i++) {
+ scanf("%d", &(seq[i]));
+ sum += seq[i];
+ if (seq[i] % 5 == 0) {
+ seq_len--;
i--;
}
}
- printf("%d\n", sum - maximum_profit(products, n_products, dividers));
+ printf("%d\n", sum - maximum_profit(seq, seq_len, k));
}