GAS_STATION

class Solution {
public:
    //greedy
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sumg = 0;
        int sumc = 0;

        for (int i = 0; i < gas.size(); ++i) {
            sumg += gas[i];
            sumc += cost[i];
        }

        if (sumg < sumc) {
            return -1;
        }
        int total = 0, ans = 0;
        //we know that unique answer exists
        for (int i = 0; i < gas.size(); ++i) {
            total += gas[i] - cost[i];

            if (total < 0) {
                total = 0;
                ans = i + 1;
            }
        }


        return ans;
    }
};