#include #include #include using namespace std; class Solution { public: int maxArea(int h, int w, vector& horizontalCuts, vector& verticalCuts); }; int Solution::maxArea(int h, int w, vector& hc, vector& vc) { long long mh, mv; size_t i; /* Add the edges of the cake to the cuts. */ hc.push_back(0); vc.push_back(0); hc.push_back(h); vc.push_back(w); /* Sort them so that adjacent cuts are adjacent in the vectors. */ sort(hc.begin(), hc.end()); sort(vc.begin(), vc.end()); mh = 0; mv = 0; /* Calculate the maximum distance between horizontal cuts */ for (i = 1; i < hc.size(); i++) { if (hc[i] - hc[i-1] > mh) mh = hc[i] - hc[i-1]; } /* Calculate the maximum distance between verticl cuts */ for (i = 1; i < vc.size(); i++) { if (vc[i] - vc[i-1] > mv) mv = vc[i] - vc[i-1]; } /* Return the product modulo that big number. */ return (mh * mv) % 1000000007; }