a bit of greedy: SPOJ - CHOCOLA

Problem Statement
SPOJ - CHOCOLA

Solution:
Greedy Algorithm: We choose the highest cost cut each time until no cut is left.
Proof of optimality:
Firstly notice that the number of cuts needed no matter how we do the cutting is C(n,m) = n+m+n*m, and this can be easily proven by induction. So the total number of cuts is always the same. Now the problem asked us to minimize the cost function \(S = a_1 w_1 + a_2 w_2 + \ldots + a_N w_N\) where \(w_i\) is the cost of cutting a certain edge, while \(a_i\) is the corresponding coefficients. The coefficient \(a_i\) is determined by the total number of cuts we done using edge \(w_i\) at the end of the cutting process. Notice that sum of the coefficients are always constant, hence we want to find a distribution of \(a_i\) obtainable such that S is minimum. To do so we claim that by performing cuts on highest cost edge as early as possible, we can reach optimal S. If we encounter several edges having the same cost, we can cut any one of them first, since in the end we will cut them all up as early as possible, hence end up with the same coefficient \(a_i\). The proof goes as follows:
Without loss of generality let \(w_1 \leq w_2 \leq w_3  \leq \ldots \leq w_N\).  Let \(O\) be another optimal cutting of \(S\) that have same coefficients different from that of \(S\). Let \(w_m\) be the highest cost edge such that the coefficient in O does not tally with that of S. This means that \(a_m\) in O will definitely be larger than that of S, since the one in S is the smallest possible \(a_m\) obtainable as we do the cutting as early as possible. Indeed, if \(a_m\) is smaller, then we have 2 cases:
1. Some of \(a_i\) in O before \(a_m\) are bigger or smaller than that of S as the result. Then this contradicts the fact that \(a_m\) is the first to deviate from S.
2. None of \(a_i\) in O is affected by the deviation in \(a_m\). This is only possible if the cut \(w_m\) is independent of the cut made in \(w_i\) before \(w_m\). But that only means that \(a_m\) is already the minimum possible, hence to have a smaller value will be a contradiction.
Hence \(a_m\) must be bigger, and hence there are some \(a_j\) after \(a_m\) in O that are smaller as the result to make up the difference. This difference is over \(w_j\) which are smaller than \(w_m\), hence in the end we will have \(S < O\), a contradiction since O is optimal. Hence S must have been optimal in the first place.

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

/* SPOJ: CHOCOLA
Idea: Greedy Algorithm Stays Ahead
The number of breaks needed is always the same.
#Proof:
C(n,m) = n + m + n*m
C(0,0) = 0 (a single box choclate needs 0 cut)
Cut horizontally:
C(n,m) = 1 + C(a,m) + C(b,m) such that a+b+1 = n
C(n,m) = 1 + a+m+a*m + b+m+b*m
       = 1 + (n-1) + 2*m + (n-1)*m
       = n + m + n*m   :)
equally for vertical cut
#
Observation: the problem is similar to weight distribution problem
Observation: each cut will happen sooner or later
Observation: the "weight" of a cut is non decreasing
Observation: if a vertical and horizontal cost are equal, cutting 
order does not matter. Proof?
So we greedily choose the largest cut-cost each time
*/

int x[1003], y[1003];

int main(){
    int tc;
    cin >> tc;
    while(tc--){
        int m,n;
        cin >> m >> n;
        for(int i=1;i<m;++i){
            cin >> x[i];
        }
        for(int i=1;i<n;++i){
            cin >> y[i];
        }
        int h = 1,v=1;
        sort(x+1,x+m);
        reverse(x+1,x+m);
        sort(y+1,y+n);
        reverse(y+1,y+n);
        int i=1,j=1;
        int ans = 0;
        while(i<m && j<n){
            if(x[i] > y[j]){
                ans += x[i]*v;
                ++h;
                ++i;
            } else {
                ans += y[j]*h;
                ++v;
                ++j;
            }
        }
        if(i<m){
            int sum = 0;
            while(i<m){
                sum += x[i];
                ++i;
            }
            ans += sum*v;
        } else {
            int sum = 0;
            while(j<n){
                sum += y[j];
                ++j;
            }
            ans += sum*h;
        }
        cout << ans << endl;
    }
    return 0;
}