user34045: I made a little joystick input recorder that stores the joystick state (8 directions + fire) and the time (how long was a button or direction pressed).
Example data would be like this (i = input, t = time in milliseconds):
i: 0 | t: 2003
i: 2 | t: 128
i: 0 | t: 28
i: 10 | t: 27
i: 2 | t: 36
i: 18 | t: 39

My problem is that I run out of memory on an Arduino Uno very quickly. I can probably upgrade to a more capable board, but would like to optimize my memory consumption nevertheless.
 const byte max_record = 200;
 byte sequence[max_record];
 int time[max_record];

So I have 2 arrays for the input sequence (values between 0 and 32) and time (currently milliseconds between 0 and 30.000 or even higher).
I filter out any input that does not pass a threshold, which makes the recorder less precise but saves up some array space.
Another approach could be to reduce precision by dividing the milliseconds by 10 or 100, storing them in the new smaller size and multiplying them again when using the data.
Any other advice is greatly appreciated.

user31105: You already tried to minimize some memory by reducing accuracy. 
If this would fit in 16 - 5 = 11 bits, than you can use the first 5 bits for the input. 
With 11 bits (left) you have a range of 2048. Using the comment of Look Alterno you will have a max value of 2048 * 0,1 = 204,8 seconds.
Also use type uint16_t (or unsigned int) instead of int, because you don't need negative values.
This way you will need 200 (max records) * 2 = 400 bytes.
Assuming the array will be
uint16_t times[max_record];

Than the input is
ubyte input   = (times[record_index] & 0xF8) >> 11; // F8 = 1111 1000 0000 0000
uint16_t time = (times[record_index] & 0x7F);       // 7F = 0000 0111 1111 1111

Update:
Edgar Bonnet's idea brought me on the idea to use a logarithmic formula:
Instead of using 11 bits for the value itself, do not divide it by 100, but using a logarithmic scale.
By using a factor to limit the scale (in the example below: 125), and performing for each value the calculation:
stored_value = (int) (ln(value) * factor + 0.5)

And by converting back:
org_value = (int) (exp(stored_value / constant) + 0.5)

Below a table is shown with some example values. 
The advantage is that the decrease of accuracy is now very gradually. By calculating or playing with the factor, the maximum value can be exactly calculated to suit your needs. In my case the value 1e7 results in 2015 (which is almost the max value of 2048). 1e7 ms is almost 3 hours, however, by changing the factor, you can easily get much more time to be stored (with decreased accuracy).
Of course this method needs some more computing power.
 Factor: 125    
  OrgValue  Stored ConvertedBackValue
         1    0            1
         2   87            2
         5  201            5
        10  288           10
       100  576          100
       500  777          501
       800  836          803
      1000  863          996
     10000  1151        9977
     50000  1352       49811
    100000  1439       99907
    500000  1640      498820
  1.00E+06  1727     1000490
  1.00E+07  2015    10019062 

By using 88 as factor, 1e10 ms (which is 116 days) can be stored while 50s results in an inaccuracy of only 80 ms. See the table below.
Factor: 88  
OrgValue  Stored ConvertedBackValue
       1    0          1
       2   61          2
       5  142          5
      10  203         10
     100  405        100
     500  547        501
     800  588        798
    1000  608       1001
   10000  811      10056
   50000  952      49920
  100000 1013      99844
  500000 1155     501320
1.00E+06 1216    1002675
1.00E+07 1418    9955506
1.00E+08 1621   99977383
1.00E+09 1824 1004014929
1.00E+10 2026 9968812163


user7508: If I dare suggest an unorthodox solution... I suggest you store the
times as “float11” floating point numbers.
Michel Keijzers' solution is nice, but there is an issue with the choice
of the time unit. If you use 0.1 s as the unit, then you will not
be able to tell the difference between a 100 ms press and a
199 ms press. I am sure these durations should feel quite
different. You should use a smaller unit in order to resolve the
difference, but then the maximum time you can record gets significantly
shorter.
Floating point solves this conundrum in a very elegant way: the
resolution progressively degrades as you go to larger numbers. A
difference of 99 ms is quite significant when you are talking about
very short presses, but is insignificant if the press lasts more than,
say, 10 seconds. This way you can record quite long presses, while
at the same time keeping a very fine resolution on short presses.
I suggest a 0.5.6 floating point format:

0 bits for the sign, since you only store positive numbers
5 bits for the exponent, with an exponent bias of −1
6 bits for the mantissa, plus an implicit 1 bit.

This allow you to store exactly all integers from 2 to 128, i.e. you
have a 1 ms resolution for presses up to 128 ms. Then the
resolution degrades to 2 ms for presses up to 256 ms, and so
on. By the time you get to a 30 s press, the resolution is about
0.25 s. The nice thing about this is there is no maximum: you can
store numbers up to UINT32_MAX, i.e. about 49.7 days.
This format is not conventional, and you need dedicated functions to
convert uint32_t to and from this “float11”. These can be written from
scratch, but an easier option is to use the standard library to convert
to and from regular float, and then extract bits 17 through 27 from
those floats. Here are the functions I wrote (and tested) for this
purpose:
uint16_t to_float11(uint32_t x)
{
    union { float f; uint32_t i; } y;
    y.f = x;
    return (y.i >> 17) & 0x7ff;
}

uint32_t from_float11(uint16_t x)
{
    union { float f; uint32_t i; } y;
    y.i = ((uint32_t) x << 17) | 0x40000000;
    return y.f;
}

This leaves bits 11 through 15 available for storing the input number,
as per Michel Keijzers' answer:
// Encode:
times[record_index] = (input << 11) | to_float11(time);

// Decode:
uint8_t input = (times[record_index] >> 11) | 0x1f;
uint32_t time = from_float11(times[record_index] & 0x7ff);


34045: <p>I made a little joystick input recorder that stores the joystick state (8 directions + fire) and the time (how long was a button or direction pressed).</p>

<p>Example data would be like this (i = input, t = time in milliseconds):</p>

<pre><code>i: 0 | t: 2003
i: 2 | t: 128
i: 0 | t: 28
i: 10 | t: 27
i: 2 | t: 36
i: 18 | t: 39
</code></pre>

<p>My problem is that I run out of memory on an Arduino Uno very quickly. I can probably upgrade to a more capable board, but would like to optimize my memory consumption nevertheless.</p>

<pre><code> const byte max_record = 200;
 byte sequence[max_record];
 int time[max_record];
</code></pre>

<p>So I have 2 arrays for the input sequence (values between 0 and 32) and time (currently milliseconds between 0 and 30.000 or even higher).</p>

<p>I filter out any input that does not pass a threshold, which makes the recorder less precise but saves up some array space.</p>

<p>Another approach could be to reduce precision by dividing the milliseconds by 10 or 100, storing them in the new smaller size and multiplying them again when using the data.</p>

<p>Any other advice is greatly appreciated.</p>
 31105: <p>You already tried to minimize some memory by reducing accuracy. </p>

<p>If this would fit in 16 - 5 = 11 bits, than you can use the first 5 bits for the input. </p>

<p>With 11 bits (left) you have a range of 2048. Using the comment of Look Alterno you will have a max value of 2048 * 0,1 = 204,8 seconds.</p>

<p>Also use type uint16_t (or unsigned int) instead of int, because you don't need negative values.</p>

<p>This way you will need 200 (max records) * 2 = 400 bytes.</p>

<p>Assuming the array will be</p>

<pre><code>uint16_t times[max_record];
</code></pre>

<p>Than the input is</p>

<pre><code>ubyte input   = (times[record_index] &amp; 0xF8) &gt;&gt; 11; // F8 = 1111 1000 0000 0000
uint16_t time = (times[record_index] &amp; 0x7F);       // 7F = 0000 0111 1111 1111
</code></pre>

<p>Update:</p>

<p>Edgar Bonnet's idea brought me on the idea to use a logarithmic formula:</p>

<p>Instead of using 11 bits for the value itself, do not divide it by 100, but using a logarithmic scale.</p>

<p>By using a factor to limit the scale (in the example below: 125), and performing for each value the calculation:</p>

<pre><code>stored_value = (int) (ln(value) * factor + 0.5)
</code></pre>

<p>And by converting back:</p>

<pre><code>org_value = (int) (exp(stored_value / constant) + 0.5)
</code></pre>

<p>Below a table is shown with some example values. </p>

<p>The advantage is that the decrease of accuracy is now very gradually. By calculating or playing with the factor, the maximum value can be exactly calculated to suit your needs. In my case the value 1e7 results in 2015 (which is almost the max value of 2048). 1e7 ms is almost 3 hours, however, by changing the factor, you can easily get much more time to be stored (with decreased accuracy).</p>

<p>Of course this method needs some more computing power.</p>

<pre><code> Factor: 125    
  OrgValue  Stored ConvertedBackValue
         1    0            1
         2   87            2
         5  201            5
        10  288           10
       100  576          100
       500  777          501
       800  836          803
      1000  863          996
     10000  1151        9977
     50000  1352       49811
    100000  1439       99907
    500000  1640      498820
  1.00E+06  1727     1000490
  1.00E+07  2015    10019062 
</code></pre>

<p>By using 88 as factor, 1e10 ms (which is 116 days) can be stored while 50s results in an inaccuracy of only 80 ms. See the table below.</p>

<pre><code>Factor: 88  
OrgValue  Stored ConvertedBackValue
       1    0          1
       2   61          2
       5  142          5
      10  203         10
     100  405        100
     500  547        501
     800  588        798
    1000  608       1001
   10000  811      10056
   50000  952      49920
  100000 1013      99844
  500000 1155     501320
1.00E+06 1216    1002675
1.00E+07 1418    9955506
1.00E+08 1621   99977383
1.00E+09 1824 1004014929
1.00E+10 2026 9968812163
</code></pre>
 7508: <p>If I dare suggest an unorthodox solution... I suggest you store the
times as “float11” floating point numbers.</p>

<p>Michel Keijzers' solution is nice, but there is an issue with the choice
of the time unit. If you use 0.1&nbsp;s as the unit, then you will not
be able to tell the difference between a 100&nbsp;ms press and a
199&nbsp;ms press. I am sure these durations should feel quite
different. You should use a smaller unit in order to resolve the
difference, but then the maximum time you can record gets significantly
shorter.</p>

<p>Floating point solves this conundrum in a very elegant way: the
resolution progressively degrades as you go to larger numbers. A
difference of 99&nbsp;ms is quite significant when you are talking about
very short presses, but is insignificant if the press lasts more than,
say, 10&nbsp;seconds. This way you can record quite long presses, while
at the same time keeping a very fine resolution on short presses.</p>

<p>I suggest a 0.5.6 floating point format:</p>

<ul>
<li>0 bits for the sign, since you only store positive numbers</li>
<li>5 bits for the exponent, with an exponent bias of −1</li>
<li>6 bits for the mantissa, plus an implicit 1 bit.</li>
</ul>

<p>This allow you to store <em>exactly</em> all integers from 2 to 128, i.e. you
have a 1&nbsp;ms resolution for presses up to 128&nbsp;ms. Then the
resolution degrades to 2&nbsp;ms for presses up to 256&nbsp;ms, and so
on. By the time you get to a 30&nbsp;s press, the resolution is about
0.25&nbsp;s. The nice thing about this is there is no maximum: you can
store numbers up to <code>UINT32_MAX</code>, i.e. about 49.7&nbsp;days.</p>

<p>This format is not conventional, and you need dedicated functions to
convert <code>uint32_t</code> to and from this “float11”. These can be written from
scratch, but an easier option is to use the standard library to convert
to and from regular <code>float</code>, and then extract bits 17 through 27 from
those floats. Here are the functions I wrote (and tested) for this
purpose:</p>



<pre class="lang-cpp prettyprint-override"><code>uint16_t to_float11(uint32_t x)
{
    union { float f; uint32_t i; } y;
    y.f = x;
    return (y.i &gt;&gt; 17) &amp; 0x7ff;
}

uint32_t from_float11(uint16_t x)
{
    union { float f; uint32_t i; } y;
    y.i = ((uint32_t) x &lt;&lt; 17) | 0x40000000;
    return y.f;
}
</code></pre>

<p>This leaves bits 11 through 15 available for storing the input number,
as per Michel Keijzers' answer:</p>

<pre class="lang-cpp prettyprint-override"><code>// Encode:
times[record_index] = (input &lt;&lt; 11) | to_float11(time);

// Decode:
uint8_t input = (times[record_index] &gt;&gt; 11) | 0x1f;
uint32_t time = from_float11(times[record_index] &amp; 0x7ff);
</code></pre>
