The ply on the one I just did was in pretty good shape, other than some rotted areas. Same story, rusty screws with large heads on top, even rustier nuts on bottom. Angle grinder made short work of that project. Working on top, start the blade in the plywood just in front of the screw, and cutting down at an angle down to just under the screw head, then proceed to cut the heads off. Takes longer to type it than it does to do it. About 1 minute per screw is about all it takes. You'll get pretty good at it about the time you're done! Push the remaining part of the screw down and out the bottom and the only thing left to do is collect them below the deck. I used a magnet.
This project would easily pay for an angle grinder (Harbor Freight) if you don't have access to one. The screws are soft enough where I think I just used one blade for the whole mess.
Oh, BTW, watch for the screw head to jump just a hair as the cut is complete. DO NOT TOUCH THAT SCREW HEAD ! It'll be hotter than blazes..... Fine, I'm reminding others of this because I was reminded the hard way.