A major goal in neuroscience is to elucidate the principles by which memories are stored in a neural network. Here, we have systematically studied how the four types of associative memories (short- and long-term memories, each as positive and negative associations) are encoded within the compact neural network of C. elegans worms. For this, we generated a transgenic animal expressing the genetically-encoded calcium indicator GCaMP in all 60 ciliated sensory neurons, and used a fast-scanning confocal system to simultaneously measure activity from all chemosensory neurons with cellular resolution. Interestingly, short-term, but not long-term, memories are evident in the sensory system, where individual sensory neurons code either the conditioned stimulus or the experience valence, or both. Long-term memories are relegated to the deeper interneuron layer of the network, allowing the sensory system to quickly resume innate functionality. Interneurons integrated the modulated sensory inputs and a simple linear combination model of sensory activities sufficed to explain the interneurons activity. The widely-distributed memory suggests that integrated network plasticity, rather than changes in individual neurons, underlies the fine behavioral plasticity. This comprehensive study reveals basic memory-coding principles and highlights the central roles of sensory neurons in memory formation.