Cutting Boards

  • + 0 comments
    #!/bin/python3
    
    import math
    import os
    import random
    import re
    import sys
    
    #
    # Complete the 'boardCutting' function below.
    #
    # The function is expected to return an INTEGER.
    # The function accepts following parameters:
    #  1. INTEGER_ARRAY cost_y
    #  2. INTEGER_ARRAY cost_x
    #
    
    def boardCutting(cost_y, cost_x):
        MOD = 10**9 + 7
        
        # Combine the cost arrays and sort them
        all_costs = sorted([(cost, 'h') for cost in cost_y] + [(cost, 'v') for cost in cost_x], reverse=True)
        
        # Initialize variables
        horizontal_segments = 1
        vertical_segments = 1
        total_cost = 0
        
        # Process each cut in sorted order
        for cost, cut_type in all_costs:
            if cut_type == 'h':
                total_cost = (total_cost + cost * vertical_segments) % MOD
                horizontal_segments += 1
            elif cut_type == 'v':
                total_cost = (total_cost + cost * horizontal_segments) % MOD
                vertical_segments += 1
        
        return total_cost
    
    if __name__ == '__main__':
    
        q = int(input().strip())
    
        for q_itr in range(q):
            first_multiple_input = input().rstrip().split()
    
            m = int(first_multiple_input[0])
    
            n = int(first_multiple_input[1])
    
            cost_y = list(map(int, input().rstrip().split()))
    
            cost_x = list(map(int, input().rstrip().split()))
    
            result = boardCutting(cost_y, cost_x)
            print(result)