문제
n개의 행렬 M1, M2, ..., Mn 이 주어진다. 행렬 Mi (i = 1, 2, ..., n)은 R[i]개의 행, C[i]개의 열을 가지고 있다 (R[i] x C[i]).
정수 i(1 ≤ i ≤ n)에 대해서, 아래와 같이 정의되는 값 Vi를 계산하려고 한다.
먼저, i개의 행렬 M1, M2, ..., Mi을 모두 곱할 수 있는 순서가 있는지 알아본다. 참고로 행렬 곱셈 연산에서 RxC 행렬과 R'xC' 행렬을 곱하려면 C = R'이 성립하여야 하고 결과로 나오는 행렬은 RxC'이다. 만약 i개의 행렬을 (순서를 자유롭게 재배치 하더라도) 곱하는 것이 불가능하다면 Vi = 0 으로 정의된다. 만약 가능하다면, 가능한 모든 방법 중 최종 결과가 되는 행렬의 크기가 가장 커지는 방법을 찾아 그 때 결과로 나온 행렬의 크기 (행의 수 x 열의 수)가 Vi 값이 된다.
V1, V2, ..., Vn를 구해보자.
출력
총 n줄을 출력해야 하고, 각 줄에는 V1 부터 Vn까지 Vi 값을 출력한다.
서브태스크 1 (5점)
- 1 ≤ n ≤ 10
- 1 ≤ R, C ≤ 1,000
서브태스크 2 (10점)
- 1 ≤ n ≤ 1,000
- 1 ≤ R, C ≤ 1,000
i = 1 일 때에는 8x2 행렬 (M1) 하나만 이용하여 원소의 수가 총 16개인 행렬을 만들 수 있다.
i = 2 일 때에는 M1 x M2 를 하여 8x8 행렬을 만들 수 있고, 원소의 수는 총 64개이다. 혹은 M2 x M1 을 하여 2x2 행렬을 만들 수 있지만, 원소의 수가 최대가 되는 방법은 상기한 방법이다.
i = 3 일 때에는 M1 x M3 x M2를 통해 8x8 행렬을 만들 수 있다.
i = 3일 때 어떤 순서로 3개의 행렬을 배치하여 곱하더라도 행렬 곱셈 연산을 완료할 수 없으므로 답이 0이다.
W3sicHJvYmxlbV9pZCI6IjE1OTMzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTg5XHViODJjIFx1YWNmMVx1YzE0OCIsImRlc2NyaXB0aW9uIjoiPHA+blx1YWMxY1x1Yzc1OCBcdWQ1ODlcdWI4MmMgTTxzdWI+MTxcL3N1Yj4sIE08c3ViPjI8XC9zdWI+LCAuLi4sIE08c3ViPm48XC9zdWI+IFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDU4OVx1YjgyYyBNPHN1Yj5pPFwvc3ViPiAoaSA9IDEsIDIsIC4uLiwgbilcdWM3NDAgUltpXVx1YWMxY1x1Yzc1OCBcdWQ1ODksIENbaV1cdWFjMWNcdWM3NTggXHVjNWY0XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQgKFJbaV0geCBDW2ldKS48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjMjE4IGkoMSAmbGU7IGkgJmxlOyBuKVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHViNDE4XHViMjk0IFx1YWMxMiBWPHN1Yj5pPFwvc3ViPlx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIGlcdWFjMWNcdWM3NTggXHVkNTg5XHViODJjIE08c3ViPjE8XC9zdWI+LCBNPHN1Yj4yPFwvc3ViPiwgLi4uLCBNPHN1Yj5pPFwvc3ViPlx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhY2YxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjMTFjXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1NGNcdWM1NDRcdWJjZjhcdWIyZTQuIFx1Y2MzOFx1YWNlMFx1Yjg1YyBcdWQ1ODlcdWI4MmMgXHVhY2YxXHVjMTQ4IFx1YzVmMFx1YzBiMFx1YzVkMFx1YzExYyBSeEMgXHVkNTg5XHViODJjXHVhY2ZjIFImIzM5O3hDJiMzOTsgXHVkNTg5XHViODJjXHVjNzQ0IFx1YWNmMVx1ZDU1OFx1YjgyNFx1YmE3NCBDID0gUiYjMzk7XHVjNzc0IFx1YzEzMVx1YjliZFx1ZDU1OFx1YzVlY1x1YzU3YyBcdWQ1NThcdWFjZTAgXHVhY2IwXHVhY2ZjXHViODVjIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWQ1ODlcdWI4MmNcdWM3NDAgUnhDJiMzOTtcdWM3NzRcdWIyZTQuIFx1YjljY1x1YzU3ZCBpXHVhYzFjXHVjNzU4IFx1ZDU4OVx1YjgyY1x1Yzc0NCAoXHVjMjFjXHVjMTFjXHViOTdjIFx1Yzc5MFx1YzcyMFx1Yjg2ZFx1YWM4YyBcdWM3YWNcdWJjMzBcdWNlNTggXHVkNTU4XHViMzU0XHViNzdjXHViM2M0KSBcdWFjZjFcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCBWPHN1Yj5pPFwvc3ViPiA9IDAgXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1YjQxY1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCwgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWJjMjlcdWJjOTUgXHVjOTExIFx1Y2Q1Y1x1Yzg4NSBcdWFjYjBcdWFjZmNcdWFjMDAgXHViNDE4XHViMjk0IFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Y2VlNFx1YzljMFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjYzNlXHVjNTQ0IFx1YWRmOCBcdWI1NGMgXHVhY2IwXHVhY2ZjXHViODVjIFx1YjA5OFx1YzYyOCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVkMDZjXHVhZTMwIChcdWQ1ODlcdWM3NTggXHVjMjE4IHggXHVjNWY0XHVjNzU4IFx1YzIxOClcdWFjMDAgVjxzdWI+aTxcL3N1Yj4gXHVhYzEyXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+VjxzdWI+MTxcL3N1Yj4sIFY8c3ViPjI8XC9zdWI+LCAuLi4sIFY8c3ViPm48XC9zdWI+XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4Jm5ic3A7blx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQgKDEgJmxlOyBuJm5ic3A7JmxlOyZuYnNwOzEsMDAwKS4gXHViMmU0XHVjNzRjIG5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggXHViNDUwIFx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsIFx1YWMwMSBcdWQ1ODlcdWI4MmNcdWM3NTggXHVkNTg5XHVjNzU4IFx1YzIxOCBSW2ldXHVjNjQwIFx1YzVmNFx1Yzc1OCBcdWMyMTggQ1tpXVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQ1ODlcdWM3NTggXHVjMjE4XHVjNjQwIFx1YzVmNFx1Yzc1OCBcdWMyMThcdWIyOTQgMSBcdWM3NzRcdWMwYzEgMSwwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2QxZCBuXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgVjxzdWI+MTxcL3N1Yj4gXHViZDgwXHVkMTMwIFY8c3ViPm48XC9zdWI+XHVhZTRjXHVjOWMwIFY8c3ViPmk8XC9zdWI+IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic3VidGFzazEiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyZuYnNwO24gJmxlOyZuYnNwOzEwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyZuYnNwO1IsIEMgJmxlOyAxLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazIiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyZuYnNwO24gJmxlOyZuYnNwOzEsMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBSLCBDICZsZTsgMSwwMDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5pID0gMSBcdWM3N2MgXHViNTRjXHVjNWQwXHViMjk0IDh4MiBcdWQ1ODlcdWI4MmMgKE08c3ViPjE8XC9zdWI+KSBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVjZDFkIDE2XHVhYzFjXHVjNzc4IFx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+aSA9IDIgXHVjNzdjIFx1YjU0Y1x1YzVkMFx1YjI5NCBNPHN1Yj4xPFwvc3ViPiB4IE08c3ViPjI8XC9zdWI+IFx1Yjk3YyBcdWQ1NThcdWM1ZWMgOHg4IFx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVjNmQwXHVjMThjXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWNkMWQgNjRcdWFjMWNcdWM3NzRcdWIyZTQuIFx1ZDYzOVx1Yzc0MCBNPHN1Yj4yPFwvc3ViPiB4IE08c3ViPjE8XC9zdWI+IFx1Yzc0NCBcdWQ1NThcdWM1ZWMgMngyIFx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzljMFx1YjljYywgXHVjNmQwXHVjMThjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWMwYzFcdWFlMzBcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5pID0gMyBcdWM3N2MgXHViNTRjXHVjNWQwXHViMjk0IE08c3ViPjE8XC9zdWI+IHggTTxzdWI+MzxcL3N1Yj4geCBNPHN1Yj4yPFwvc3ViPlx1Yjk3YyBcdWQxYjVcdWQ1NzQgOHg4IFx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8zIjoiPHA+aSA9IDNcdWM3N2MgXHViNTRjIFx1YzViNFx1YjVhNCBcdWMyMWNcdWMxMWNcdWI4NWMgM1x1YWMxY1x1Yzc1OCBcdWQ1ODlcdWI4MmNcdWM3NDQgXHViYzMwXHVjZTU4XHVkNTU4XHVjNWVjIFx1YWNmMVx1ZDU1OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWQ1ODlcdWI4MmMgXHVhY2YxXHVjMTQ4IFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWM2NDRcdWI4Y2NcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YzczY1x1YmJjMFx1Yjg1YyBcdWIyZjVcdWM3NzQgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIxNTkzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1hdHJpeCBNdWx0aXBsaWNhdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBuIG1hdHJpY2VzLCBsYWJlbGVkIGFzIE08c3ViPjE8XC9zdWI+LCBNPHN1Yj4yPFwvc3ViPiwgLi4uLCBNPHN1Yj5uPFwvc3ViPi4gTWF0cml4IE08c3ViPmk8XC9zdWI+ICh3aGVyZSBpID0gMSwgMiwgLi4uLCBuKSBoYXMgUltpXSByb3dzIGFuZCBDW2ldIGNvbHVtbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIGkgYmV0d2VlbiAxIGFuZCBuIChpbmNsdXNpdmUpLCB5b3Ugd2FudCB0byBjb21wdXRlIGEgbnVtYmVyICh3ZSBjYWxsIFY8c3ViPmk8XC9zdWI+KSBhcyBmb2xsb3dzLjxcL3A+XHJcblxyXG48cD5Vc2luZyB0aGUgbWF0cmljZXMgTTxzdWI+MTxcL3N1Yj4sIE08c3ViPjI8XC9zdWI+LCAuLi4sIE08c3ViPmk8XC9zdWI+LCB5b3Ugd2lsbCBmaXJzdCBkZXRlcm1pbmUgaWYgeW91IGNhbiBmaW5kIGFuIG9yZGVyaW5nIG9mIHRoZXNlIGkgbWF0cmljZXMgc3VjaCB0aGF0IHlvdSBjYW4gbXVsdGlwbHkgYWxsIGkgb2YgdGhlbS4gTm90ZSB0aGF0IHR3byBtYXRyaWNlcyBvZiBzaXplIFJ4QyBhbmQgUiYjMzk7eEMmIzM5OyBjYW4gYmUgbXVsdGlwbGllZCBpZiBhbmQgb25seSBpZiBDID0gUiYjMzk7LCBhbmQgdGhlIHJlc3VsdGluZyBtYXRyaXggaXMgb2Ygc2l6ZSBSeEMmIzM5Oy4gSWYgdGhpcyBpcyBpbXBvc3NpYmxlLCBWPHN1Yj5pPFwvc3ViPiA9IDAuIElmIHRoaXMgaXMgcG9zc2libGUsIHRoZW4gVjxzdWI+aTxcL3N1Yj4gaXMgZGVmaW5lZCBhcyB0aGUgc2l6ZSBvZiB0aGUgbGFyZ2VzdCBtYXRyaXggeW91IGNhbiBvYnRhaW4gaW4gdGhpcyBtYW5uZXIuIEluIG90aGVyIHdvcmRzLCBhbW9uZyBhbGwgb3JkZXJpbmdzIG9mIHRoZSBpIG1hdHJpY2VzLCBWPHN1Yj5pPFwvc3ViPiBpcyB0aGUgbWF4aW11bSBudW1iZXIgb2YgZWxlbWVudHMgZm91bmQgaW4gdGhlIG1hdHJpeCB0aGF0IGlzIHRoZSBwcm9kdWN0IG9mIHRoZSBpIG1hdHJpY2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGFza2VkIHRvIGNvbXB1dGUgdGhlIHZhbHVlcyBWPHN1Yj4xPFwvc3ViPiwgVjxzdWI+MjxcL3N1Yj4sIC4uLiwgVjxzdWI+bjxcL3N1Yj4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgbiAoMSAmbGU7Jm5ic3A7biAmbGU7IDEsMDAwKS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbnMgdHdvIG51bWJlcnMgZWFjaCwgZGVub3RpbmcgdGhlIG51bWJlciBvZiByb3dzIGFuZCB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgb2YgYSBtYXRyaXguICZuYnNwO1RoZSBudW1iZXIgb2Ygcm93cyBhbmQgdGhlIG51bWJlciBvZiBjb2x1bW5zIG9mIGVhY2ggbWF0cml4IGlzIGJldHdlZW4gMSBhbmQgMSwwMDAsIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3UgbXVzdCBvdXRwdXQgbiBsaW5lcyB3aGVyZSB0aGUgaS10aCBsaW5lIGNvbnRhaW5zIHRoZSB2YWx1ZSBWPHN1Yj5pPFwvc3ViPiBkZXNjcmliZWQgaW4gdGhlIHByb2JsZW0gc3RhdGVtZW50LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzdWJ0YXNrMSI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7Jm5ic3A7biAmbGU7Jm5ic3A7MTA8XC9saT5cclxuXHQ8bGk+MSAmbGU7Jm5ic3A7UiwgQyAmbGU7IDEsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7Jm5ic3A7biAmbGU7Jm5ic3A7MSwwMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IFIsIEMgJmxlOyAxLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPldoZW4gaSA9IDEsIHRoZSBhbnN3ZXIgaXMgdHJpdmlhbGx5IDE2IGFzIE08c3ViPjE8XC9zdWI+IGNvbnRhaW5zIDE2IGVsZW1lbnRzLjxcL3A+XHJcblxyXG48cD5XaGVuIGkgPSAyLCB3ZSBjYW4gbXVsdGlwbHkgdGhlbSAoTTxzdWI+MTxcL3N1Yj4geCBNPHN1Yj4yPFwvc3ViPikgdG8gb2J0YWluIGEgOCB4IDggbWF0cml4LjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgd2UgY2FuIGFsc28gbXVsdGlwbHkgdGhlbSBpbiB0aGUgb3RoZXIgb3JkZXIgKE08c3ViPjI8XC9zdWI+IHggTTxzdWI+MTxcL3N1Yj4pIHRvIG9idGFpbiBhIDIgeCAyIG1hdHJpeCwgYnV0IGl0IGlzIG5vdCBtYXhpbXVtLjxcL3A+XHJcblxyXG48cD5XaGVuIGkgPSAzLCB3ZSBjYW4gbXVsdGlwbHkgdGhlIHRocmVlIG1hdHJpY2VzIGFzIE08c3ViPjE8XC9zdWI+IHggTTxzdWI+MzxcL3N1Yj4geCBNPHN1Yj4yPFwvc3ViPiwgdG8gb2J0YWluIGEgOCB4IDggbWF0cml4LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzMiOiI8cD5UaGVyZSBpcyBubyBvcmRlcmluZyB0aGF0IHJlc3VsdHMgaW4gYSB2YWxpZCBtYXRyaXggbXVsdGlwbGljYXRpb24gb2YgdGhlIHRocmVlIG1hdHJpY2VzLiZuYnNwOzxcL3A+XHJcbiJ9XQ==