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

문제

정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러 번 더해도 된다)

수열이 주어졌을 때, 총 몇 개의 수가 좋은 수 일까?

입력

첫째 줄에 수열 A의 크기 N이 주어진다. (1 ≤ N ≤ 5000) 둘째 줄에는 수열 A의 각 숫자가 공백으로 구분되어 주어진다. (-100,000 ≤ Ai ≤ 100,000)

출력

첫째 줄에 좋은 수의 개수를 출력한다.

예제 입력 1

2
1 3

예제 출력 1

1

예제 입력 2

6
1 2 3 5 7 10

예제 출력 2

4

예제 입력 3

3
-1 2 0

예제 출력 3

1
W3sicHJvYmxlbV9pZCI6IjU2MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4OGJcdWM3NDAgXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMyMTggTlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0IEFcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMsIGlcdWJjODhcdWM5ZjggXHVjMjE4XHVhYzAwIFx1YWRmOCBcdWM1NWVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YWRmOCBcdWMyMThcdWI5N2MgXHVjODhiXHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gKFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yjk3YyBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YjM1NFx1ZDU3NFx1YjNjNCBcdWI0MWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkMWQgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVjODhiXHVjNzQwIFx1YzIxOCBcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNTAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM1ZjQgQVx1Yzc1OCBcdWFjMDEgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwMCwwMDAgJmxlOyBBPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4OGJcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTYyNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRPQlJJIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIGEgc2VxdWVuY2UgQSBjb25zaXN0aW5nIG9mIE4gaW50ZWdlcnMgKG5vdCB0byBiZSBjb25mdXNlZCB3aXRoIHRoZSBzZXF1ZW5jZSBmcm9tIHRoZSBwcmV2aW91cyB0YXNrKS4gV2Ugd2lsbCBjYWxsIHRoZSBpPHN1cD50aDxcL3N1cD4gc2VxdWVuY2UgZWxlbWVudCBnb29kIGlmIGl0IGVxdWFscyB0aGUgc3VtIG9mIHNvbWUgdGhyZWUgZWxlbWVudHMgaW4gcG9zaXRpb25zIHN0cmljdGx5IHNtYWxsZXIgdGhhbiBpIChhbiBlbGVtZW50IGNhbiBiZSB1c2VkIG1vcmUgdGhhbiBvbmNlIGluIHRoZSBzdW0pLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ib3cgbWFueSBnb29kIGVsZW1lbnRzIGRvZXMgdGhlIHNlcXVlbmNlIGNvbnRhaW4/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDUwMDApLCB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSBBLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgcmVwcmVzZW50aW5nIHRoZSBzZXF1ZW5jZSBBICgtMTAwIDAwMCAmbGU7IEE8c3ViPmk8XC9zdWI+ICZsZTsgMTAwIDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbnVtYmVyIG9mIGdvb2QgZWxlbWVudHMgaW4gdGhlIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #6 3번