1 files changed, 38 insertions, 22 deletions

diff --git a/Practical2/c/checkout.c b/Practical2/c/checkout.c
index 7c39a0b..82eda3a 100644
--- a/Practical2/c/checkout.c
+++ b/Practical2/c/checkout.c
@@ -11,47 +11,63 @@ uint32_t round_ct(uint32_t cents) {
     }
 }
 
-uint32_t minimum_payment(uint16_t products[], uint16_t n_products, uint8_t dividers) {
-    uint32_t minimums[n_products+1][dividers+1];
-    uint32_t last[n_products+1][dividers+1];
-
-    uint16_t p, d, q;
+int32_t maximum_profit(uint16_t products[], uint16_t n_products, uint8_t dividers) {
+    uint32_t sums[n_products+1][n_products+1];
+    uint16_t i, j;
+    for (i = 0; i <= n_products; i++) {
+        for (j = 0; j <= n_products; j++) {
+            if (j <= i) {
+                sums[i][j] = 0;
+            } else if (j == 1) {
+                sums[i][j] = products[0];
+            } else {
+                sums[i][j] = sums[i][j-1] + products[j-1];
+            }
+        }
+    }
 
+    int32_t profit[n_products+1][dividers+1];
+    uint16_t p, d;
     for (p = 0; p <= n_products; p++) {
         for (d = 0; d <= dividers; d++) {
-            if (p == 0 || d == 0) {
-                uint32_t sum = 0;
-                for (q = 0; q < n_products && q < p; q++)
-                    sum += products[q];
-                minimums[p][d] = round_ct(sum);
-                last[p][d] = sum;
+            if (p == 0) {
+                profit[p][d] = 0;
+            } else if (d == 0) {
+                profit[p][d] = sums[0][p] - round_ct(sums[0][p]);
             } else {
-                uint16_t try1 = minimums[p-1][d] - round_ct(last[p-1][d]) + round_ct(last[p-1][d] + products[p-1]);
-                uint16_t try2 = minimums[p-1][d-1] + round_ct(products[p-1]);
-                if (try1 < try2) {
-                    minimums[p][d] = try1;
-                    last[p][d] = last[p-1][d] + products[p-1];
-                } else {
-                    minimums[p][d] = try2;
-                    last[p][d] = products[p-1];
+                int32_t max = profit[p][d-1];
+                uint16_t i;
+                for (i = 0; i < p; i++) {
+                    int32_t try = profit[i][d-1] + sums[i][p] - round_ct(sums[i][p]);
+                    if (try > max)
+                        max = try;
                 }
+                profit[p][d] = max;
             }
         }
     }
 
-    return minimums[n_products][dividers];
+    return profit[n_products][dividers];
 }
 
 int main(void) {
     int n_products;
     int dividers;
+    uint32_t sum = 0;
+
     scanf("%d %d", &n_products, &dividers);
 
     uint16_t products[n_products];
     uint16_t i;
-    for (i = 0; i < n_products; i++)
+    for (i = 0; i < n_products; i++) {
         scanf("%d", &(products[i]));
+        sum += products[i];
+        if (products[i] % 5 == 0) {
+            n_products--;
+            i--;
+        }
+    }
 
-    printf("%d\n", minimum_payment(products, n_products, dividers));
+    printf("%d\n", sum - maximum_profit(products, n_products, dividers));
 }