Simulate NPDAs with DTMs using only polynomial overhead
We can combine two known techniques: CYK -which you mention- and the PDA to CFL construction.

Assume that the PDA is in "Chomsky Normal Form": it reads iff it pops, and pushes two symbols otherwise.
Formally, its instructions are of the form 


$(p,\varepsilon,A) \mapsto (q,BC)$
$(p,a,A) \mapsto (q,\varepsilon)$


Recall that this can be transformed into CFL using non-terminals of the type $[p,A,r]$, and the productions


$[p,A,r] \to [q,B,s][s,C,r]$ for any "guessed" states $r,s$
$[p,A,q] \to a$


Note that $[p,A,r]$ is a non-terminal that derives all strings using certain computations (see below).

We do not have to explicitly perform the latter construction, but we can build it in the CYK itself, by introducing a table $P(i,j)$ that contains elements that are such triplets. So this would mean $[p,A,r] \in P(i,j)$ iff there is a computation on $w_i\dots w_j$ starting in state $p$ and ending in state $r$ that starts with $A$ on the stack and ends with an empty stack.