What's the action? That will be the verb. Who's doing the action? That will be the subject. What is the action applied to? That will be the direct object.
verb: Signed. That's the action. Good. subject: Government. That's who's doing the signing. Good. direct object: What's being signed? It's the memorandum, not the company, right?
"Company" is an object, but it's the object of the preposition "with."
Prepositional phrases modify other parts of the sentence. You've got three in your example: