50137. Stack Rectangles

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define max(a,b) ((a)>(b)?(a):(b))

typedef struct{
    int w;
    int l;
} s_box;

int arr_sum(int lst[], int n){
    int s = 0;
    for(int i = 0; i < n; i++) s += lst[i];
    return s;
}

int n;
s_box box[256];

int can_stack(s_box* a, s_box* b){ // a < b
    if(a->w <= b->w && a->l <= b->l) return 1;
    if(a->w <= b->l && a->l <= b->w) return 1;
    return 0;
}

int max_size = -1;
int max_sum_idx = -1;
void dfs(int arr[], int arr_size, int now_idx){
    // (n - now_idx): from now on all choose
    if(arr_size + (n - now_idx) < max_size) return;
    if(now_idx == n){
        if(arr_size < max_size) return;
        int sum_idx = arr_sum(arr, arr_size);
        if(arr_size > max_size){
            max_size = arr_size;
            max_sum_idx = sum_idx;
        }
        else if(arr_size == max_size){
            max_sum_idx = max(max_sum_idx, sum_idx);
        }
    }
    else{
        // choose (is possible)
        if(arr_size == 0 || can_stack(&box[now_idx], &box[arr[arr_size - 1]])){
            arr[arr_size] = now_idx;
            dfs(arr, arr_size + 1, now_idx + 1);
            arr[arr_size] = 0;
        }

        // no choose
        dfs(arr, arr_size, now_idx + 1);
    }
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        int a, b; scanf("%d %d", &a, &b);
        box[i].w = a, box[i].l = b;
    }

    int arr[256] = {0};
    dfs(arr, 0, 0);
    printf("%d %d\n", max_size, max_sum_idx);
}