시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 16 4 4 100.000%

문제

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이 주어진다 (1 ≤ n ≤ 1,000). 다음 n줄에는 각 줄에 정수 두 개가 주어지는데, 각 행렬의 행의 수 R[i]와 열의 수 C[i]이다. 각 행렬의 행의 수와 열의 수는 1 이상 1,000 이하이다.

출력

총 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

예제 입력 1

3
8 2
2 8
2 2

예제 출력 1

16
64
64

i = 1 일 때에는 8x2 행렬 (M1) 하나만 이용하여 원소의 수가 총 16개인 행렬을 만들 수 있다.

i = 2 일 때에는 M1 x M2 를 하여 8x8 행렬을 만들 수 있고, 원소의 수는 총 64개이다. 혹은 M2 x M1 을 하여 2x2 행렬을 만들 수 있지만, 원소의 수가 최대가 되는 방법은 상기한 방법이다.

i = 3 일 때에는 M1 x M3 x M2를 통해 8x8 행렬을 만들 수 있다.

예제 입력 2

3
4 9
9 1
9 9

예제 출력 2

36
4
4

예제 입력 3

3
4 10
10 1
10 6

예제 출력 3

40
4
0

i = 3일 때 어떤 순서로 3개의 행렬을 배치하여 곱하더라도 행렬 곱셈 연산을 완료할 수 없으므로 답이 0이다.

예제 입력 4

3
10 3
3 10
5 5

예제 출력 4

30
100
0

예제 입력 5

4
1 1
1 1
1 1
1 1

예제 출력 5

1
1
1
1
W3sicHJvYmxlbV9pZCI6IjE1OTMzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTg5XHViODJjIFx1YWNmMVx1YzE0OCIsImRlc2NyaXB0aW9uIjoiPHA+blx1YWMxY1x1Yzc1OCBcdWQ1ODlcdWI4MmMgTTxzdWI+MTxcL3N1Yj4sIE08c3ViPjI8XC9zdWI+LCAuLi4sIE08c3ViPm48XC9zdWI+IFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDU4OVx1YjgyYyBNPHN1Yj5pPFwvc3ViPiAoaSA9IDEsIDIsIC4uLiwgbilcdWM3NDAgUltpXVx1YWMxY1x1Yzc1OCBcdWQ1ODksIENbaV1cdWFjMWNcdWM3NTggXHVjNWY0XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQgKFJbaV0geCBDW2ldKS48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjMjE4IGkoMSAmbGU7IGkgJmxlOyBuKVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHViNDE4XHViMjk0IFx1YWMxMiBWPHN1Yj5pPFwvc3ViPlx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIGlcdWFjMWNcdWM3NTggXHVkNTg5XHViODJjIE08c3ViPjE8XC9zdWI+LCBNPHN1Yj4yPFwvc3ViPiwgLi4uLCBNPHN1Yj5pPFwvc3ViPlx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhY2YxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjMTFjXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1NGNcdWM1NDRcdWJjZjhcdWIyZTQuIFx1Y2MzOFx1YWNlMFx1Yjg1YyBcdWQ1ODlcdWI4MmMgXHVhY2YxXHVjMTQ4IFx1YzVmMFx1YzBiMFx1YzVkMFx1YzExYyBSeEMgXHVkNTg5XHViODJjXHVhY2ZjIFImIzM5O3hDJiMzOTsgXHVkNTg5XHViODJjXHVjNzQ0IFx1YWNmMVx1ZDU1OFx1YjgyNFx1YmE3NCBDID0gUiYjMzk7XHVjNzc0IFx1YzEzMVx1YjliZFx1ZDU1OFx1YzVlY1x1YzU3YyBcdWQ1NThcdWFjZTAgXHVhY2IwXHVhY2ZjXHViODVjIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWQ1ODlcdWI4MmNcdWM3NDAgUnhDJiMzOTtcdWM3NzRcdWIyZTQuIFx1YjljY1x1YzU3ZCBpXHVhYzFjXHVjNzU4IFx1ZDU4OVx1YjgyY1x1Yzc0NCAoXHVjMjFjXHVjMTFjXHViOTdjIFx1Yzc5MFx1YzcyMFx1Yjg2ZFx1YWM4YyBcdWM3YWNcdWJjMzBcdWNlNTggXHVkNTU4XHViMzU0XHViNzdjXHViM2M0KSBcdWFjZjFcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCBWPHN1Yj5pPFwvc3ViPiA9IDAgXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1YjQxY1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCwgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWJjMjlcdWJjOTUgXHVjOTExIFx1Y2Q1Y1x1Yzg4NSBcdWFjYjBcdWFjZmNcdWFjMDAgXHViNDE4XHViMjk0IFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Y2VlNFx1YzljMFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjYzNlXHVjNTQ0IFx1YWRmOCBcdWI1NGMgXHVhY2IwXHVhY2ZjXHViODVjIFx1YjA5OFx1YzYyOCBcdWQ1ODlcdWI4MmNcdWM3NTggXHVkMDZjXHVhZTMwIChcdWQ1ODlcdWM3NTggXHVjMjE4IHggXHVjNWY0XHVjNzU4IFx1YzIxOClcdWFjMDAgVjxzdWI+aTxcL3N1Yj4gXHVhYzEyXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+VjxzdWI+MTxcL3N1Yj4sIFY8c3ViPjI8XC9zdWI+LCAuLi4sIFY8c3ViPm48XC9zdWI+XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4Jm5ic3A7blx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQgKDEgJmxlOyBuJm5ic3A7JmxlOyZuYnNwOzEsMDAwKS4gXHViMmU0XHVjNzRjIG5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggXHViNDUwIFx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsIFx1YWMwMSBcdWQ1ODlcdWI4MmNcdWM3NTggXHVkNTg5XHVjNzU4IFx1YzIxOCBSW2ldXHVjNjQwIFx1YzVmNFx1Yzc1OCBcdWMyMTggQ1tpXVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWQ1ODlcdWM3NTggXHVjMjE4XHVjNjQwIFx1YzVmNFx1Yzc1OCBcdWMyMThcdWIyOTQgMSBcdWM3NzRcdWMwYzEgMSwwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2QxZCBuXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgVjxzdWI+MTxcL3N1Yj4gXHViZDgwXHVkMTMwIFY8c3ViPm48XC9zdWI+XHVhZTRjXHVjOWMwIFY8c3ViPmk8XC9zdWI+IFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0Iiwic3VidGFzazEiOiI8dWw+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+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCIsInN1YnRhc2sxIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsmbmJzcDtuICZsZTsmbmJzcDsxMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsmbmJzcDtSLCBDICZsZTsgMSwwMDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2syIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsmbmJzcDtuICZsZTsmbmJzcDsxLDAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgUiwgQyAmbGU7IDEsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+V2hlbiBpID0gMSwgdGhlIGFuc3dlciBpcyB0cml2aWFsbHkgMTYgYXMgTTxzdWI+MTxcL3N1Yj4gY29udGFpbnMgMTYgZWxlbWVudHMuPFwvcD5cclxuXHJcbjxwPldoZW4gaSA9IDIsIHdlIGNhbiBtdWx0aXBseSB0aGVtIChNPHN1Yj4xPFwvc3ViPiB4IE08c3ViPjI8XC9zdWI+KSB0byBvYnRhaW4gYSA4IHggOCBtYXRyaXguPFwvcD5cclxuXHJcbjxwPk5vdGUgdGhhdCB3ZSBjYW4gYWxzbyBtdWx0aXBseSB0aGVtIGluIHRoZSBvdGhlciBvcmRlciAoTTxzdWI+MjxcL3N1Yj4geCBNPHN1Yj4xPFwvc3ViPikgdG8gb2J0YWluIGEgMiB4IDIgbWF0cml4LCBidXQgaXQgaXMgbm90IG1heGltdW0uPFwvcD5cclxuXHJcbjxwPldoZW4gaSA9IDMsIHdlIGNhbiBtdWx0aXBseSB0aGUgdGhyZWUgbWF0cmljZXMgYXMgTTxzdWI+MTxcL3N1Yj4geCBNPHN1Yj4zPFwvc3ViPiB4IE08c3ViPjI8XC9zdWI+LCB0byBvYnRhaW4gYSA4IHggOCBtYXRyaXguPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwPlRoZXJlIGlzIG5vIG9yZGVyaW5nIHRoYXQgcmVzdWx0cyBpbiBhIHZhbGlkIG1hdHJpeCBtdWx0aXBsaWNhdGlvbiBvZiB0aGUgdGhyZWUgbWF0cmljZXMuJm5ic3A7PFwvcD5cclxuIn1d

출처

  • 문제를 만든 사람: haden
  • 데이터를 추가한 사람: jh05013