Did you swim along the ocean floor after being ejected by sub?
Did you search the seaweed?
Go left four screens from the cliff ( or look below where sub was ).