How can I make the code for a problem use less memory to pass a test?

Question

I'm trying to solve a problem I found online, but I keep getting a memory error.

You need to knit a scarf, for one . loop you need K millimeters of rope, and for / and | loops you need M and P millimeters accordingly. The goal is to find how many skeins with the length of H you need to finish the scarf.

You input 2 variables in the first line: T, R.

And in the second line you input: K, M, P and H.

Then you input T rows with R charachters in each.

An example:

Input:

3 20
4 7 4 128
|...|//./|..|||..|./
../....||/...||.|/||
|||///||/.|||///|//.

Output:

3

The problem is being tested with this file.

How can I possibly make the code use less memory?

I tried using this code I wrote:

#include <iostream>

using namespace std;

int main() {
    int t, r, k, m, p, h, a, ans, i, j;
    ans = 0;
    a = 0;
    cin >> t >> r;
    string knit[t];
    cin >> k >> m >> p >> h;
    for (i = 0; i < t; i++) {
        cin >> knit[i];
    }
    for (i = 0; i < t; i++) {
        for (j = 0; j < r; j++) {
            if (knit[i][j] == '.') {
                a += k;
            }
            
            else if (knit[i][j] == '/') {
                a += m;
            }
            
            else {
                a += p;
            }
        }
    }
    while (a > 0) {
        a -= h;
        ans++;
    }
    cout << ans;
}

It works fine, but I keep getting a memory limit error.

Answer 1

I made the following improvements to your routine:

• There's now a need to create an array, we only need to allocate enough memory for 1 line.
• I over-allocate the memory needed, i.e. allow for 1024 characters in the line, but we will only process the input length
• I use a lookup table to map the stitch patterns to the number
• Finally, I use an integer math to compute the result needed - it implements roundup by pre adding (h - 1) before dividing by h

#include <iostream>

using namespace std;

int main() {
    int t, r;
    cin >> t >> r;
    int k, m, p, h;
    cin >> k >> m >> p >> h;
    int table[256] = { };
    table['.'] = k;
    table['/'] = m;
    table['|'] = p;
    int x = 0;
    for (int i =0; i < t; i++) {
         char line[1024] = { };
         cin >> line;
         for (int j = 0; j < r; j++) {
             x += table[line[j]];
         }
    }
    cout << ((x + h - 1) / h) << '\n';
    return 0;
}