def max_cost(smaller=True, single=True, negative=False): """ :param smaller: False = (重さ = W)の時の最大価値 True = (重さ =< W)の時の最大価値 :param single: False = 重複あり :param negative: True = 負の価値の物が混入している dp[weight (== W)の時の最小価値 :param single: False = 重複あり dp[weight (<=W)] = 重さを固定した時の最小価値 dp[W+1] = 重さがWより大きい時の最小価値 path_restoring = [(weight,cost), (weight,cost),...] = 最適コストを実現する組み合わせ """ N=len(weight_list) dp_max = INF # 総和価値の最大値 dp = [dp_max] * (W+2) dp[0] = 0 # 重さ 0 の時は価値 0 parent = [(-1,-1)]*(W+2) for item in range(N): if single: S = range(W+2)[::-1] else: S = range(W+2) for weight in S: if dp[min(weight + weight_list[item], W+1)] > dp[weight] + cost_list[item]: dp[min(weight+weight_list[item],W+1)]=dp[weight] + cost_list[item] parent[min(weight+weight_list[item],W+1)]=(weight,item) if larger: if dp[W] y else y def min2(x,y): return x if x < y else y ########################################################## def example(): global input example = iter( """ 5 11 2 9 5 4 7 2 9 4 6 10 """ .strip().split("\n")) input = lambda: next(example) ########################################################## import sys from bisect import * input = sys.stdin.readline # example() N, K = map(int, input().split()) # N: 品物の種類 W: 重量制限 cost_list = [] weight_list = [] for k in range(1,K+1): """ cost と weight が逆転して入力されている場合有り """ weight, cost = k**2, k cost_list.append(cost) weight_list.append(weight) W=N cost,path=min_cost(larger=False,single=False) res=[["."]*cost for _ in range(cost)] k0=0 for _,k in path: for h in range(k0,k0+k): for w in range(k0,k0+k): res[h][w]="#" k0+=k for h in range(cost): print("".join(res[h]))