PROBLEM LINK:
VILLINE - Recruit Villagers ENIGMA-Plinth’20
Author - priyam2k
Editorialist - Priyam Khandelwal
DIFFICULTY:
Easy
PREREQUISITES:
Basic Maths
PROBLEM:
Given an equation of a line and n points and their associated values, find what is the maximum sum of values on either side of the line.
Explanation
It is well known that if you put a point in the equation of a line, there are 3 possible cases.
1.) Value comes out to be 0 i.e. Point is on the line.
2.) Value comes out to be positive i.e. Point is on one side of the line.
3.) Value comes out to be negative i.e. Point is on the other side of the line.
So, you have to sum all the positive values together and all negative values together, then find which is greater.