시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 15 10 8 61.538%

문제

알렉스는 창고에서 어렸을 때 가지고 놀던 막대 N개를 찾았다. 막대의 길이는 A1, A2, ..., AN이며, 모두 2보다 크거나 같은 자연수이다.

오늘은 이 막대를 이용해서 직사각형을 만들려고 한다. 각 막대는 최대 한 번 사용할 수 있고, 여러 개의 막대를 이용해서 직사각형의 한 변을 만드는 것은 불가능하다. 일부 막대는 직사각형을 만들 때 사용하지 않아도 된다. 직사각형은 하나 이상을 만들어도 된다.

알렉스는 막대의 길이를 1만큼만 줄일 수 있는 기계를 하나 만들었다. 막대의 길이가 Ai라면, 막대의 길이를 Ai-1로 줄여서 사용할 수 있다. 기계를 사용하는 횟수는 제한이 없지만, 길이를 줄인 막대를 또 줄일 수는 없다.

알렉스는 만든 직사각형의 넓이의 합이 최대가 되게 직사각형을 만들려고 한다. 이 때, 그 넓이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 막대의 개수 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에는 막대의 길이 A1, A2, ..., AN이 주어진다. (2 ≤ Ai ≤ 100,000)

출력

알렉스가 만든 직사각형의 넓이의 합의 최댓값을 출력한다.

예제 입력 1

4
5 5 6 6

예제 출력 1

30

예제 입력 2

4
4 5 2 3

예제 출력 2

8

변의 길이가 2, 4인 직사각형을 만들 수 있다.

예제 입력 3

4
2 4 6 8

예제 출력 3

0

예제 입력 4

6
5 6 6 3 4 4

예제 출력 4

24

예제 입력 5

9
10 3 4 4 4 5 6 6 6

예제 출력 5

42

길이가 5, 6, 6, 6인 막대 중에서 길이가 6인 막대 하나의 길이를 5로 줄여 넓이가 30인 직사각형을 만들 수 있다. 그 다음, 길이가 3, 4, 4, 4인 막대 중에서 길이가 4인 막대 하나의 길이를 3으로 줄여 넓이가 12인 직사각형을 만들 수 있다.

이 외의 다른 방법은 넓이의 합이 42를 넘지 않는다.

예제 입력 6

10
10 10 10 10 10 10 10 10 10 10

예제 출력 6

200

예제 입력 7

4
100000 100000 100000 100000

예제 출력 7

10000000000
W3sicHJvYmxlbV9pZCI6IjE2MjA3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NGNcdWI4MDlcdWMyYTRcdWIyOTQgXHVjYzNkXHVhY2UwXHVjNWQwXHVjMTFjIFx1YzViNFx1YjgzOFx1Yzc0NCBcdWI1NGMgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YjE4MFx1YjM1OCBcdWI5YzlcdWIzMDAgTlx1YWMxY1x1Yjk3YyBcdWNjM2VcdWM1NThcdWIyZTQuIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgQTxzdWI+MTxcL3N1Yj4sIEE8c3ViPjI8XC9zdWI+LCAuLi4sIEE8c3ViPk48XC9zdWI+XHVjNzc0XHViYTcwLCBcdWJhYThcdWI0NTAgMlx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHViMjk4XHVjNzQwIFx1Yzc3NCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHViOWM5XHViMzAwXHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHViYzg4IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YjljOVx1YjMwMFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDU1YyBcdWJjYzBcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuIFx1Yzc3Y1x1YmQ4MCBcdWI5YzlcdWIzMDBcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWI1NGMmbmJzcDtcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQwIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0XHViM2M0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTRjXHViODA5XHVjMmE0XHViMjk0IFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgMVx1YjljY1x1ZDA3Y1x1YjljYyBcdWM5MDRcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFlMzBcdWFjYzRcdWI5N2MgXHVkNTU4XHViMDk4IFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gXHViOWM5XHViMzAwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBBPHN1Yj5pPFwvc3ViPlx1Yjc3Y1x1YmE3NCwgXHViOWM5XHViMzAwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBBPHN1Yj5pPFwvc3ViPi0xXHViODVjIFx1YzkwNFx1YzVlY1x1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZTMwXHVhY2M0XHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWQ2OWZcdWMyMThcdWIyOTQgXHVjODFjXHVkNTVjXHVjNzc0IFx1YzVjNlx1YzljMFx1YjljYywgXHVhZTM4XHVjNzc0XHViOTdjIFx1YzkwNFx1Yzc3OCBcdWI5YzlcdWIzMDBcdWI5N2MgXHViNjEwIFx1YzkwNFx1Yzc3YyBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NGNcdWI4MDlcdWMyYTRcdWIyOTQmbmJzcDtcdWI5Y2NcdWI0ZTAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjExM1x1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YWM4YyBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVhZGY4IFx1YjExM1x1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWM5XHViMzAwXHVjNzU4IFx1YWMxY1x1YzIxOCBOKDEgJmxlOyBOICZsZTsgMTAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWM5XHViMzAwXHVjNzU4IFx1YWUzOFx1Yzc3NCBBPHN1Yj4xPFwvc3ViPiwgQTxzdWI+MjxcL3N1Yj4sIC4uLiwgQTxzdWI+TjxcL3N1Yj5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IEE8c3ViPmk8XC9zdWI+ICZsZTsgMTAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM1NGNcdWI4MDlcdWMyYTRcdWFjMDAgXHViOWNjXHViNGUwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMTNcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0Iiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgMiwgNFx1Yzc3OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fNSI6IjxwPlx1YWUzOFx1Yzc3NFx1YWMwMCA1LCA2LCA2LCA2XHVjNzc4IFx1YjljOVx1YjMwMCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhZTM4XHVjNzc0XHVhYzAwIDZcdWM3NzggXHViOWM5XHViMzAwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgNVx1Yjg1YyBcdWM5MDRcdWM1ZWMgXHViMTEzXHVjNzc0XHVhYzAwIDMwXHVjNzc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgXHVhZTM4XHVjNzc0XHVhYzAwIDMsIDQsIDQsIDRcdWM3NzggXHViOWM5XHViMzAwIFx1YzkxMVx1YzVkMFx1YzExYyBcdWFlMzhcdWM3NzRcdWFjMDAgNFx1Yzc3OCBcdWI5YzlcdWIzMDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyAzXHVjNzNjXHViODVjIFx1YzkwNFx1YzVlYyBcdWIxMTNcdWM3NzRcdWFjMDAgMTJcdWM3NzggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjNjc4XHVjNzU4IFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3NDAgXHViMTEzXHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc3NCA0Mlx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjE2MjA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmVjdGFuZ2xlcyIsImRlc2NyaXB0aW9uIjoiPHA+QWxleCBmb3VuZCBOIHN0aWNrcyB0aGF0IGhlIHBsYXllZCB3aXRoIHdoZW4gaGUgd2FzIGxpdHRsZS4gU3RpY2tzJnJzcXVvOyBsZW5ndGhzIGFyZSBBPHN1Yj4xPFwvc3ViPiwgQTxzdWI+MjxcL3N1Yj4sICZoZWxsaXA7LCBBPHN1Yj5OPFwvc3ViPiwgYW5kIHRoZSBsZW5ndGggaXMgYW4gaW50ZWdlciB0aGF0IGlzIGdyZWF0ZXIgdGhhbiBvciBlcXVhbCB0byAyLjxcL3A+XHJcblxyXG48cD5BbGV4IHdhbnRzIHRvIGNyZWF0ZSByZWN0YW5nbGVzIHVzaW5nIHRoZXNlIHN0aWNrcy4gRWFjaCBzdGljayBjYW4gYmUgdXNlZCBhdCBtb3N0IG9uY2UsIGFuZCBoZSBjYW5ub3QgdXNlIG11bHRpcGxlIHN0aWNrcyB0byBmb3JtIGEgc2lkZSBvZiB0aGUgcmVjdGFuZ2xlLiBOb3QgYWxsIHN0aWNrcyBuZWVkIHRvIGJlIHVzZWQuIEFsZXggY2FuIG1ha2UgbW9yZSB0aGFuIG9uZSByZWN0YW5nbGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFsZXggYWxzbyBoYXMgYSBtYWNoaW5lIHRoYXQgY2FuIHJlZHVjZSB0aGUgbGVuZ3RoIG9mIGEgc3RpY2sgYnkgMS4gSWYgdGhlIG9yaWdpbmFsIGxlbmd0aCBvZiBhIHN0aWNrIHdhcyBBPHN1Yj5pPFwvc3ViPiwgdGhlbiBpdCBjYW4gYmUgcmVkdWNlZCB0byBBPHN1Yj5pPFwvc3ViPi0xIHVzaW5nIHRoaXMgbWFjaGluZS4gQWxleCBjYW4gdXNlIHRoZSBtYWNoaW5lIGFzIG1hbnkgdGltZXMgYXMgaGUgd2FudHMgdG8sIGJ1dCBoZSBjYW5ub3QgcmVkdWNlIHRoZSBsZW5ndGggb2YgdGhlIHNhbWUgc3RpY2sgbW9yZSB0aGFuIG9uY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFsZXggd2FudHMgdG8gbWFrZSByZWN0YW5nbGVzIHVzaW5nIHRoZXNlIE4gc3RpY2tzIHN1Y2ggdGhhdCB0aGUgc3VtIG9mIGFyZWFzIG9mIHRoZSByZWN0YW5nbGVzIGlzIG1heGltaXplZC4gWW91IG11c3QgY29tcHV0ZSB0aGlzIG1heGltdW0gYXJlYSBoZSBjYW4gYWNoaWV2ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIE4gKDEgJmxlOyBOICZsZTsgMTAsMDAwKSwgdGhlIG51bWJlciBvZiBzdGlja3MuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBOIGludGVnZXJzIGRlc2NyaWJpbmcgdGhlIGxlbmd0aHMgb2YgTiBzdGlja3MsIEE8c3ViPjE8XC9zdWI+LCBBPHN1Yj4yPFwvc3ViPiwgLi4uLCBBPHN1Yj5OPFwvc3ViPiAoMiAmbGU7IEE8c3ViPmk8XC9zdWI+ICZsZTsgMTAwLDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtYXhpbXVtIHRvdGFsIGFyZWEgb2YgcmVjdGFuZ2xlcyBBbGV4IGNhbiBhY2hpZXZlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCIsInNhbXBsZV9leHBsYWluXzIiOiI8cD5BbGV4IGNhbiBtYWtlIGEgcmVjdGFuZ2xlIHdpdGggc2lkZXMgb2YgbGVuZ3RoIDIgYW5kIDQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fNSI6IjxwPlVzaW5nIHRoZSBsYXN0IGZvdXIgc3RpY2tzIChhZnRlciByZWR1Y2luZyBvbmUgNi1sZW5ndGggc3RpY2smcnNxdW87cyBsZW5ndGggYnkgMSksIEFsZXggY2FuIG1ha2UgYSByZWN0YW5nbGUgd2hvc2UgYXJlYSBpcyA1eDYgPSAzMC4gVGhlbiwgdXNpbmcgdGhlIG90aGVyIGZvdXIgc3RpY2tzIG9mIGxlbmd0aHMgMywgNCwgNCwgYW5kIDQsIGhlIGNhbiBtYWtlIGFub3RoZXIgcmVjdGFuZ2xlIHdob3NlIGFyZWEgaXMgM3g0ID0gMTIuIFRoZXJlIGlzIG5vIHdheSB0byBtYWtlIHJlY3RhbmdsZXMgd2hvc2Ugc3VtIG9mIGFyZWEgaXMgZ3JlYXRlciB0aGFuIDQyLjxcL3A+XHJcbiJ9XQ==

출처

  • 문제를 만든 사람: haden