시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB51181339.394%

문제

창영이의 수학 공책에는 길이가 N이고 정수로 이루어진 수열 두 개가 적혀져 있다. 두 수열의 흐릿함을 계산하려면, 두 번째 수열을 뒤집은 다음, 같은 위치에 있는 두 수의 곱을 더해야 한다.

3 -4 -3 -2 2 0
-3 0 5 -1 3 2

예를 들어, 위의 두 수열의 흐릿함은 3×2 + (-4)×3 + (-3)×(-1) + (-2)×5 + 2×0 + 0×(-3) = -13 이다.

창영이는 앞에서부터 B개, 뒤에서부터 E개를 지워서 두 수열의 흐릿함을 되도록 크게 만들려고 한다. B와 E는 0일 수도 있으며, 수를 지울 때는 두 수열에서 동시에 지워야 한다.

흐릿함을 가장 크게 만들려면, B와 E가 몇이 되어야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 N (1 ≤ N ≤ 2000)이 주어진다.

다음 두 줄에 걸쳐서 두 수열이 주어진다. 모든 숫자는 -1000보다 크거나 같고, 1000보다 작거나 같다.

출력

첫째 줄에 B와 E를 출력한다. (0 ≤ B, E < N, B+E < N)

둘째 줄에는 흐릿함의 최댓값을 출력한다.

흐릿함을 최대로 만드는 B와 E가 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

6
3 -4 -3 -2 2 0
-3 0 5 -1 3 2

예제 출력 1

0 3
24

예제 입력 2

5
1 1 1 1 1
2 2 2 2 2

예제 출력 2

0 0
10

예제 입력 3

5
5 -5 -5 -5 5
-5 -5 5 -5 -5

예제 출력 3

2 0
75
W3sicHJvYmxlbV9pZCI6Ijg5NzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWQ1NTkgXHVhY2Y1XHVjYzQ1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWM3NTggXHVjMjE4XHVkNTU5IFx1YWNmNVx1Y2M0NVx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3NFx1YWNlMCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNCBcdWI0NTAgXHVhYzFjXHVhYzAwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWMyMThcdWM1ZjRcdWM3NTggXHVkNzUwXHViOWJmXHVkNTY4XHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjgyNFx1YmE3NCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViNGE0XHVjOWQxXHVjNzQwIFx1YjJlNFx1Yzc0YywgXHVhYzE5XHVjNzQwIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViNDUwIFx1YzIxOFx1Yzc1OCBcdWFjZjFcdWM3NDQgXHViMzU0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWQgdGFibGUtY2VudGVyLTMwIHRkLWNlbnRlclwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPi00PFwvdGQ+XHJcblx0XHRcdDx0ZD4tMzxcL3RkPlxyXG5cdFx0XHQ8dGQ+LTI8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+LTM8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPi0xPFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM3MDRcdWM3NTggXHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQ3NTBcdWI5YmZcdWQ1NjhcdWM3NDAgMyZ0aW1lczsyICsgKC00KSZ0aW1lczszICsgKC0zKSZ0aW1lczsoLTEpICsgKC0yKSZ0aW1lczs1ICsgMiZ0aW1lczswICsgMCZ0aW1lczsoLTMpID0gLTEzIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YzU1ZVx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBCXHVhYzFjLCBcdWI0YTRcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgRVx1YWMxY1x1Yjk3YyBcdWM5YzBcdWM2Y2NcdWMxMWMgXHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQ3NTBcdWI5YmZcdWQ1NjhcdWM3NDQgXHViNDE4XHViM2M0XHViODVkIFx1ZDA2Y1x1YWM4YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBCXHVjNjQwIEVcdWIyOTQgMFx1Yzc3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWMyMThcdWI5N2MgXHVjOWMwXHVjNmI4IFx1YjU0Y1x1YjI5NCBcdWI0NTAgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM5YzBcdWM2Y2NcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ3NTBcdWI5YmZcdWQ1NjhcdWM3NDQgXHVhYzAwXHVjN2E1IFx1ZDA2Y1x1YWM4YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWJhNzQsIEJcdWM2NDAgRVx1YWMwMCBcdWJhODdcdWM3NzQgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCBOICgxICZsZTsgTiAmbGU7IDIwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YjQ1MCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YjQ1MCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMjJiXHVjNzkwXHViMjk0IC0xMDAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEJcdWM2NDAgRVx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuICgwICZsZTsgQiwgRSAmbHQ7IE4sIEIrRSAmbHQ7IE4pPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNzUwXHViOWJmXHVkNTY4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDc1MFx1YjliZlx1ZDU2OFx1Yzc0NCBcdWNkNWNcdWIzMDBcdWI4NWMgXHViOWNjXHViNGRjXHViMjk0IEJcdWM2NDAgRVx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijg5NzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOSVpPVkkiLCJkZXNjcmlwdGlvbiI6IjxwPk1hcmtvJiMzOTtzIG1hdGggbm90ZWJvb2sgaGFzIHR3byBzZXF1ZW5jZXMgb2YgaW50ZWdlcnMgd3JpdHRlbiBpbiBpdCwgYm90aCBvZiBsZW5ndGggTi4gVGhlIGZ1enppbmVzcyBvZiB0aGVzZSBzZXF1ZW5jZXMgaXMgY2FsY3VsYXRlZCBieSBmaXJzdCByZXZlcnNpbmcgdGhlIG9yZGVyIG9mIHRoZSBlbGVtZW50cyBpbiB0aGUgc2Vjb25kIHNlcXVlbmNlIGFuZCB0aGVuIGFkZGluZyB0aGUgcHJvZHVjdHMgb2YgZWxlbWVudHMgaW4gdGhlIHNhbWUgcG9zaXRpb25zIG9mIHRoZSB0d28gc2VxdWVuY2VzLiZuYnNwOzxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZCB0YWJsZS1jZW50ZXItMzAgdGQtY2VudGVyXCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+LTQ8XC90ZD5cclxuXHRcdFx0PHRkPi0zPFwvdGQ+XHJcblx0XHRcdDx0ZD4tMjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4tMzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+LTE8XC90ZD5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIGZ1enppbmVzcyBvZiB0aGUgYWJvdmUgdHdvIHNlcXVlbmNlIG9mIGxlbmd0aCA2IGlzIDMmbWlkZG90OzIgKyAoJm1pbnVzOzQpJm1pZGRvdDszICsgKCZtaW51czszKSZtaWRkb3Q7KCZtaW51czsxKSArICgmbWludXM7MikmbWlkZG90OzUgKyAyJm1pZGRvdDswICsgMCZtaWRkb3Q7KCZtaW51czszKSA9ICZtaW51czsxMy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gbGlrZXMgaGlzIHBhaXJzIG9mIHNlcXVlbmNlcyB0byBiZSBhcyBmdXp6eSBhcyBwb3NzaWJsZS4gSGUgZGVjaWRlZCB0byByZW1vdmUgQiBudW1iZXJzIChwb3NzaWJseSB6ZXJvKSBmcm9tIHRoZSBiZWdpbm5pbmcgb2YgYm90aCBzZXF1ZW5jZXMgYW5kIGFsc28gRSBudW1iZXJzIChwb3NzaWJseSB6ZXJvKSBmcm9tIHRoZSBlbmQgb2YgYm90aCBzZXF1ZW5jZXMsIHNvIHRoYXQgdGhlIGZ1enppbmVzcyBpcyBhcyBsYXJnZSBhcyBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgdGhlIHZhbHVlcyBvZiBCIGFuZCBFIGZvciB3aGljaCB0aGUgZnV6emluZXNzIGlzIGxhcmdlc3QuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDIwMDApLCB0aGUgbGVuZ3RoIG9mIE1hcmtvJiMzOTtzIHNlcXVlbmNlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyB0d28gbGluZXMgY29udGFpbiBOIGludGVnZXJzIGVhY2gsIHRoZSB0d28gc2VxdWVuY2VzLiBBbGwgbnVtYmVycyBpbiB0aGUgdHdvIHNlcXVlbmNlcyB3aWxsIGJlIGJldHdlZW4gJm1pbnVzOzEwMDAgYW5kIDEwMDAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHR3byBpbnRlZ2VycyBCIGFuZCBFIG9uIHRoZSBmaXJzdCBsaW5lLCBzdWNoIHRoYXQgMCAmbGU7IFAsIEsgJmx0OyBOIGFuZCBQK0sgJmx0OyBOLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PdXRwdXQgdGhlIHJlc3VsdGluZyBmdXp6aW5lc3Mgb24gdGhlIHNlY29uZCBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JZiBtdWx0aXBsZSBjaG9pY2VzIG9mIEIgYW5kIEUgYWNoaWV2ZSB0aGUgbGFyZ2VzdCBmdXp6aW5lc3MsIG91dHB1dCBhbnkgb2YgdGhlbS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Regional Competition - Seniors 2번