시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 128 MB85842100142723.012%

문제

Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다.

Elly는 그녀가 가르칠 수 있는 모든 학생들의 코딩 실력을 알고 있다. 각각의 코딩 실력 Ai는 -10000부터 10000 사이의 정수로 표시되어 있다. 그녀는 팀워크와 코딩 실력이 모두 적절한 팀을 만들기 위해, 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 이러한 조건 하에, 그녀가 대회에 출전할 수 있는 팀을 얼마나 많이 만들 수 있는지를 계산하여라.

N명의 학생들의 코딩 실력 Ai가 -10000부터 10000사이의 정수로 주어질 때, 합이 0이 되는 3인조를 만들 수 있는 경우의 수를 구하여라.

입력

입력은 표준 입력으로 주어진다.

첫 번째 줄에 학생의 수 N이 입력된다. 두 번째 줄에 N개의 그녀가 가르칠 학생들의 코딩 실력인 Ai가 주어진다.

출력

표준 출력으로 그녀가 고를 수 있는 팀의 수를 하나의 정수로 출력한다.

제한

  • 1 ≤ N ≤ 10000
  • -10000 ≤ Ai ≤ 10000

예제 입력 1

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

예제 출력 1

6

힌트

예시에서 가능한 참가자 그룹은 아래와 같다.

(2, -5, 3), (2, 2, -4), (2, 2, -4), (-5, 2, 3), (3, -4, 1), (3, -4, 1)

두 개의 -4는 서로 다른 참가자를 나타내는 것에 유의하라. (2, 2, -4)와 (3, -4, 1)이 두 번씩 나타난다.

W3sicHJvYmxlbV9pZCI6IjMxNTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NjlcdWM3NzQgMCIsImRlc2NyaXB0aW9uIjoiPHA+RWxseVx1YjI5NCBcdWM2MDhcdWMwYzFcdWNlNTggXHViYWJiXHVkNTU4XHVhYzhjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVjOTAwXHViZTQ0XHVkNTU4XHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0NCBcdWFjMDBcdWI5NzRcdWNlNjAgXHVjNzA0XHVhZTMwXHVjNWQwIFx1Y2M5OFx1ZDU4OFx1YjJlNC4gXHViMzAwXHVkNjhjXHViMjk0IFx1YzgxNVx1ZDY1NVx1ZDc4OCAzXHViYTg1XHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBcdWQzMDBcdWI5Y2MgXHVjYzM4XHVhYzAwXHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC4gXHVhZGY4XHViN2VjXHViMDk4IFx1YWRmOFx1YjE0MFx1YWMwMCBcdWFjMDBcdWI5NzRcdWNlNjAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNWQwXHVhYzhjXHViMjk0IFx1ZDA3MCBcdWJiMzhcdWM4MWNcdWFjMDAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWNmNTRcdWI1MjkgXHVjMmU0XHViODI1XHVjNzc0IFx1Yzg4Ylx1YzczY1x1YmE3NCZuYnNwO1x1ZDMwMFx1YzZjY1x1ZDA2Y1x1YWMwMCBcdWI1YThcdWM1YjRcdWM5YzBcdWFjZTAsIFx1ZDMwMFx1YzZjY1x1ZDA2Y1x1YWMwMCBcdWM4OGJcdWM3NDRcdWMyMThcdWI4NWQgXHVjZjU0XHViNTI5IFx1YzJlNFx1YjgyNVx1Yzc3NCBcdWI1YThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWNkOWNcdWM4MDRcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YjMwMFx1ZDY4Y1x1YjI5NCBcdWNmNTRcdWI1MjkgXHVjMmU0XHViODI1XHVhY2ZjIFx1ZDMwMFx1YzZjY1x1ZDA2YyBcdWJhYThcdWI0NTBcdWFjMDAgXHVjOTExXHVjNjk0XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5FbGx5XHViMjk0IFx1YWRmOFx1YjE0MFx1YWMwMCBcdWFjMDBcdWI5NzRcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1Y2Y1NFx1YjUyOSBcdWMyZTRcdWI4MjVcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2Y1NFx1YjUyOSBcdWMyZTRcdWI4MjUgQTxzdWI+aTxcL3N1Yj5cdWIyOTQgLTEwMDAwXHViZDgwXHVkMTMwIDEwMDAwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViMTQwXHViMjk0IFx1ZDMwMFx1YzZjY1x1ZDA2Y1x1YzY0MCBcdWNmNTRcdWI1MjkgXHVjMmU0XHViODI1XHVjNzc0Jm5ic3A7XHViYWE4XHViNDUwIFx1YzgwMVx1YzgwOFx1ZDU1YyBcdWQzMDBcdWM3NDQgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVjMTM4IFx1ZDMwMFx1YzZkMFx1Yzc1OCZuYnNwO1x1Y2Y1NFx1YjUyOSBcdWMyZTRcdWI4MjVcdWM3NTggXHVkNTY5XHVjNzc0IDBcdWM3NzQgXHViNDE4XHViMjk0IFx1ZDMwMFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjODcwXHVhYzc0IFx1ZDU1OFx1YzVkMCwgXHVhZGY4XHViMTQwXHVhYzAwIFx1YjMwMFx1ZDY4Y1x1YzVkMCBcdWNkOWNcdWM4MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQzMDBcdWM3NDQgXHVjNWJjXHViOWM4XHViMDk4IFx1YjljZVx1Yzc3NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuXHJcbjxwPk5cdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1Y2Y1NFx1YjUyOSBcdWMyZTRcdWI4MjUmbmJzcDtBPHN1Yj5pPFwvc3ViPlx1YWMwMCAtMTAwMDBcdWJkODBcdWQxMzAgMTAwMDBcdWMwYWNcdWM3NzRcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1ZDU2OVx1Yzc3NCAwXHVjNzc0IFx1YjQxOFx1YjI5NCAzXHVjNzc4XHVjODcwXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YWRmOFx1YjE0MFx1YWMwMCBcdWFjMDBcdWI5NzRcdWNlNjAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1Y2Y1NFx1YjUyOSBcdWMyZTRcdWI4MjVcdWM3NzggQTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDQ1Y1x1YzkwMCBcdWNkOWNcdWI4MjVcdWM3M2NcdWI4NWMgXHVhZGY4XHViMTQwXHVhYzAwIFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDMwMFx1Yzc1OCBcdWMyMThcdWI5N2MmbmJzcDtcdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHVjMjE4XHViODVjJm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWMyZGNcdWM1ZDBcdWMxMWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1Y2MzOFx1YWMwMFx1Yzc5MCBcdWFkZjhcdWI4ZjlcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+KDIsIC01LCAzKSwgKDIsIDIsIC00KSwgKDIsIDIsIC00KSwgKC01LCAyLCAzKSwgKDMsIC00LCAxKSwgKDMsIC00LCAxKTxcL3A+XHJcblxyXG48cD5cdWI0NTAmbmJzcDtcdWFjMWNcdWM3NTggLTRcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWNjMzhcdWFjMDBcdWM3OTBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YWM4M1x1YzVkMCBcdWM3MjBcdWM3NThcdWQ1NThcdWI3N2MuJm5ic3A7KDIsIDIsIC00KVx1YzY0MCAoMywgLTQsIDEpXHVjNzc0IFx1YjQ1MCBcdWJjODhcdWM1MjkgXHViMDk4XHVkMGMwXHViMDljXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMTAwMDA8XC9saT5cclxuXHQ8bGk+LTEwMDAwICZsZTsgQTxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IDEwMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMTUxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWmVybyBTdW0iLCJkZXNjcmlwdGlvbiI6IjxwPkVsbHkgdW5leHBlY3RlZGx5IHN0YXJ0ZWQgdGVhY2hpbmcgYSBwcm9ncmFtbWluZyBjb250ZXN0IHByZXBhcmF0aW9uIGNsYXNzLiBTb21lIG9mIHRoZSBjb250ZXN0cyB0aGVyZSBhcmUgQUNNIHN0eWxlLCBpLmUuIHRoZSBjb250ZXN0YW50cyBtdXN0IGZvcm0gdGVhbXMgb2YgZXhhY3RseSB0aHJlZSBwZXJzb25zLiBBZnRlciBzb21lIHRyYWluaW5nIGl0IGlzIHRpbWUgZm9yIGhlciBzdHVkZW50cyB0byBzaGluZSAmbmRhc2g7IHRoZSBuYXRpb25hbCBzdHVkZW50IE9seW1waWFkIGhhcyBjb21lLiBFbGx5IG11c3QgZGVjaWRlIHdoaWNoIHRocmVlIHN0dWRlbnRzIHdpbGwgcmVwcmVzZW50IGhlciBjbGFzcyBpbiB0aGUgY29udGVzdC4gVW5mb3J0dW5hdGVseSwgaGVyIHN0dWRlbnRzIGhhdmUgdGhlIGZvbGxvd2luZyBwcm9wZXJ0eTogdGhlIGJldHRlciBhdCBjb2RpbmcgdGhleSBhcmUsIHRoZSB3b3JzZSBhcmUgdGhlaXIgdGVhbSBza2lsbHM7IG9uIHRoZSBvdGhlciBoYW5kLCB0aGUgYmV0dGVyIHRoZWlyIHRlYW0gc2tpbGxzIGFyZSwgdGhlIHdvcnNlIHRoZXkgY29kZS4gQW5kIEFDTSBpcyBhIHR5cGUgb2YgY29udGVzdCwgd2hlcmUgYm90aCBnb29kIGNvZGluZyBhbmQgdGVhbSBza2lsbHMgYXJlIG5lZWRlZC48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgdGhlIHRyYWluaW5nIGFuZCBzb21lIGxvY2FsIGNvbnRlc3RzLCBFbGx5IGhhcyBhIGxpc3Qgb2YgdGhlIGNvZGluZyBza2lsbHMgb2YgYWxsIGhlciBzdHVkZW50cy4gRWFjaCBvZiB0aGUgTiBjb250ZXN0YW50cyBoYXMgYSBudW1iZXIgYmV0d2VlbiAtMTAwMDAgYW5kIDEwMDAwLCBkZW5vdGluZyBoaXMgb3IgaGVyIHNraWxsLiBTaGUgd2FudHMgdG8gZm9ybSB0aGUgdGVhbSBpbiBzdWNoIGEgd2F5LCB0aGF0IHRoZSBzdW0gb2YgdGhlIHRocmVlIGNvbnRlc3RhbnRzIGlzIHplcm8uIFRoaXMgd291bGQgbWVhbiB0aGF0IHRoZSB0ZWFtIGlzIHJlbGF0aXZlbHkgYmFsYW5jZWQgYm90aCBmb3IgY29kaW5nIGFuZCB0ZWFtIHNraWxscy4gR2l2ZW4gdGhlIHJlc3VsdHMgb2YgdGhlIHN0dWRlbnRzLCBmaW5kIGluIGhvdyBtYW55IHdheXMgc2hlIGNhbiBjaG9vc2UgdGhlIHRlYW0gZm9yIHRoZSBjb250ZXN0LjxcL3A+XHJcblxyXG48cD5XZSBjYW4gc3VtbWFyaXplIHRoZSBwcm9ibGVtIGluIHRoZSBmb2xsb3dpbmcgd2F5OiBGb3IgZ2l2ZW4gTiBpbnRlZ2VycyBiZXR3ZWVuIC0xMDAwMCBhbmQgMTAwMDAgd3JpdGUgYSBwcm9ncmFtIHplcm9zdW0sIHdoaWNoIGZpbmRzIGhvdyBtYW55ICh1bm9yZGVyZWQpIHRyaXBsZXMgd2l0aCB6ZXJvIHN1bSB0aGVyZSBhcmUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgdGhlIGludGVnZXIgTiAmbmRhc2g7IHRoZSBudW1iZXIgb2Ygc3R1ZGVudHMgd2lsbCBiZSBnaXZlbi4gT24gdGhlIHNlY29uZCBsaW5lIE4gaW50ZWdlcnMgYmV0d2VlbiAtMTAwMDAgYW5kIDEwMDAwICZuZGFzaDsgdGhlIGNvZGluZyBza2lsbCBvZiBlYWNoIHN0dWRlbnQgd2lsbCBiZSBnaXZlbi4mbmJzcDsoMSAmbGU7IE4gJmxlOyAxMDAwMCwgLTEwMDAwICZsZTsgQTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PbiB0aGUgc3RhbmRhcmQgb3V0cHV0IHByaW50IGEgc2luZ2xlIGludGVnZXIgJm5kYXNoOyB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIHRlYW1zIHNoZSBjYW4gY2hvb3NlIGZyb20uPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBwb3NzaWJsZSB0cmlwbGVzIGFyZTogKDIsIC01LCAzKSwgKDIsIDIsIC00KSwgKDIsIDIsIC00KSwgKC01LCAyLCAzKSwgKDMsIC00LCAxKSwgKDMsIC00LCAxKS4gTm90ZSB0aGF0IHRoZSB0d28gLTQgbnVtYmVycyBkZW5vdGUgZGlmZmVyZW50IGNvbnRlc3RhbnRzLiBUaHVzLCB0aGUgcmVwZWF0ZWQgdHJpcGxlICgyLCAyLCAtNCkgZ2l2ZXMgdHdvIGRpZmZlcmVudCB0ZWFtcy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > International Autumn Tournament in Informatics > 2011 > Group B (Juniors) 3번