You generally want to polypaint at the lowest level of subdivision that holds the detail to your satisfaction. If 50k polys isn’t enough, paint at a higher subd level.
The resulting texture will hold the detail if the texture image is large enough to hold the detail for the number of polys being worked on. If it isn’t you can:
-increase the size of the image to hold more detail
-optimize your mesh to deliver more polys to areas that need it, and eliminate them in areas that dont.
-optimize your UVs by using a different mapping method, or laying them out in such a manner that makes better use of available image space
These are all more complicated subjects than I can casually cover here, and will take months of experience on your part to get a feel for the best approaches in different situations.
Make sure to read the zbrush documentation:
http://docs.pixologic.com/user-guide/3d-modeling/painting-your-model/polypaint/
http://docs.pixologic.com/features/main-features/texturing/
http://docs.pixologic.com/user-guide/3d-modeling/painting-your-model/texture-maps/
And be sure to watch the videos in the zclassroom:
http://pixologic.com/zclassroom/homeroom/
Take your time, and just focus on learning how to accomplish simple achievable goals every day. You won’t learn Zbrush in a week, let alone more general 3d concepts like texturing and uv mapping. But if you focus on learning one specific thing a day, you’ll be making sense of things before you know it.
Good luck