In that case you are obviously lost your keys/coins, but that is why people are making multiple backups in different locations.
You can always put paper inside waterproof plastic bag, and than in fireproof bag, that is not expensive at all.
Much more durable alternative is to use stainless steel (washers) or titanium instead of paper.

You don't need to print anything, just use regular paper and pen.
New solutions are now offering to store keys encrypted in cards that look like regular payment cards (Satochip and Keycard).