3228번 - 극한 피자 배달

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 2 2 66.667%

문제

Picko는 피자집을 열려고한다. 생각해뒀던 몇 개의 점포가 있는데, 그 중 가게가 흥할 것만 같은 점포들을 몇개 알아두었다. 한 점포에 피자집을 열게되면, 그 피자집에서 주어진 범위 내의 모든 가구들에게 배달을 갈 수 있다.

Picko가 열 수 있는 피자집의 수는 제한이 되어 있다. 한 가구당 임의 S명의 사람들이 살고 있는데, 최적의 점포들에 입점을 해 배달 가능한 최대 사람의 수를 구하라.

입력

첫째 줄에는 정수 피잣집의 수 K(1 ≤ K ≤ 10)와 각 지점이 배달할 수 있는 최대 거리 R(1 ≤ R ≤ 500)이 주어진다.

둘째 줄에는 정수 Picko가 알아둔 점포의 수 M(K ≤ M ≤ 20)이 주어진다.

이어지는 M줄에는 각 점포의 좌표를 가리키는 정수 X와Y가 주어진다.(-1000 ≤ X,Y ≤ 1000)

그 다음 줄에는 가구의 수 N(1 ≤ N ≤ 100)이 주어진다.

이어지는 N줄에는 각 가구의 좌표 X, Y(-1000 ≤ X,Y ≤ 1000)와 몇 인 가구인지 가리키는 정수 S(1 ≤ S ≤ 100)가 주어진다.

가구로부터 점포까지의 거리가 주어진 R보다 작거나 같다면 그 가구내의 모든 사람들에게 배달이 가능하다.

출력

K개의 피잣집으로 배달 가능한 최대 사람 수를 구하라. (가구의 수가 아니다!!)

예제 입력 1 

2 2
3
1 0
4 0
7 0
4
0 0 1
3 0 7
5 0 9
8 0 1

예제 출력 1 

18

예제 입력 2 

2 2
3
-2 0
0 1
3 0
8
-3 1 1
-3 0 1
-3 -1 1
-2 -1 1
0 0 3
0 2 1
2 1 3
4 0 2

예제 출력 2 

12

예제 입력 3 

3 3
5
0 0
1 6
2 3
6 6
7 2
8
0 1 2
0 5 3
0 6 1
1 0 1
3 2 3
3 6 2
6 2 4
8 6 3

예제 출력 3 

17

힌트

W3sicHJvYmxlbV9pZCI6IjMyMjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjlcdWQ1NWMgXHVkNTNjXHVjNzkwIFx1YmMzMFx1YjJlYyIsImRlc2NyaXB0aW9uIjoiPHA+UGlja29cdWIyOTQgXHVkNTNjXHVjNzkwXHVjOWQxXHVjNzQ0IFx1YzVmNFx1YjgyNFx1YWNlMFx1ZDU1Y1x1YjJlNC4gXHVjMGRkXHVhYzAxXHVkNTc0XHViNDgwXHViMzU4IFx1YmE4NyBcdWFjMWNcdWM3NTggXHVjODEwXHVkM2VjXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVhZGY4IFx1YzkxMSBcdWFjMDBcdWFjOGNcdWFjMDAgXHVkNzY1XHVkNTYwIFx1YWM4M1x1YjljYyBcdWFjMTlcdWM3NDAgXHVjODEwXHVkM2VjXHViNGU0XHVjNzQ0IFx1YmE4N1x1YWMxYyBcdWM1NGNcdWM1NDRcdWI0NTBcdWM1YzhcdWIyZTQuIFx1ZDU1YyBcdWM4MTBcdWQzZWNcdWM1ZDAgXHVkNTNjXHVjNzkwXHVjOWQxXHVjNzQ0IFx1YzVmNFx1YWM4Y1x1YjQxOFx1YmE3NCwgXHVhZGY4IFx1ZDUzY1x1Yzc5MFx1YzlkMVx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYzk0XHVjNzA0IFx1YjBiNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVhYzAwXHVhZDZjXHViNGU0XHVjNWQwXHVhYzhjIFx1YmMzMFx1YjJlY1x1Yzc0NCBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+UGlja29cdWFjMDAgXHVjNWY0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNTNjXHVjNzkwXHVjOWQxXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWM4MWNcdWQ1NWNcdWM3NzQgXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVkNTVjIFx1YWMwMFx1YWQ2Y1x1YjJmOSBcdWM3ODRcdWM3NTggU1x1YmE4NVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjZDVjXHVjODAxXHVjNzU4IFx1YzgxMFx1ZDNlY1x1YjRlNFx1YzVkMCBcdWM3ODVcdWM4MTBcdWM3NDQgXHVkNTc0IFx1YmMzMFx1YjJlYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDVjXHViMzAwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggXHVkNTNjXHVjN2EzXHVjOWQxXHVjNzU4IFx1YzIxOCBLKDEgJmxlOyBLICZsZTsgMTApXHVjNjQwIFx1YWMwMSBcdWM5YzBcdWM4MTBcdWM3NzQgXHViYzMwXHViMmVjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YWM3MFx1YjlhYyBSKDEgJmxlOyBSICZsZTsgNTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IFBpY2tvXHVhYzAwIFx1YzU0Y1x1YzU0NFx1YjQ1NCBcdWM4MTBcdWQzZWNcdWM3NTggXHVjMjE4IE0oSyAmbGU7IE0gJmxlOyAyMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM1YjRcdWM5YzBcdWIyOTQgTVx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjODEwXHVkM2VjXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWFjMDBcdWI5YWNcdWQwYTRcdWIyOTQgXHVjODE1XHVjMjE4IFhcdWM2NDBZXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4oLTEwMDAgJmxlOyBYLFkgJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWFkNmNcdWM3NTggXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IE5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YWMwMFx1YWQ2Y1x1Yzc1OCBcdWM4OGNcdWQ0NWMgWCwgWSgtMTAwMCAmbGU7IFgsWSAmbGU7IDEwMDApXHVjNjQwIFx1YmE4NyBcdWM3NzggXHVhYzAwXHVhZDZjXHVjNzc4XHVjOWMwIFx1YWMwMFx1YjlhY1x1ZDBhNFx1YjI5NCBcdWM4MTVcdWMyMTggUygxICZsZTsgUyAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWFkNmNcdWI4NWNcdWJkODBcdWQxMzAgXHVjODEwXHVkM2VjXHVhZTRjXHVjOWMwXHVjNzU4IFx1YWM3MFx1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzQgUlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0XHViYTc0IFx1YWRmOCBcdWFjMDBcdWFkNmNcdWIwYjRcdWM3NTggXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWJjMzBcdWIyZWNcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPktcdWFjMWNcdWM3NTggXHVkNTNjXHVjN2EzXHVjOWQxXHVjNzNjXHViODVjIFx1YmMzMFx1YjJlYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDVjXHViMzAwIFx1YzBhY1x1Yjc4YyBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViNzdjLiAoXHVhYzAwXHVhZDZjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQhISk8XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMyMjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQSVpaQSIsImRlc2NyaXB0aW9uIjoiPHA+T3VyIGZyaWVuZCBQaWNrbyBpcyB2ZXJ5IHJlYWNoIGFuZCBoZSB3YW50cyB0byBvcGVuIGxvdHMgb2YgcmVzdGF1cmFudHMgd2l0aCBkZWxpdmVyeS4gVGhhIG1haW4gZm9vZCB3aWxsIGJlLCBvZiBjb3Vyc2UsIHBpenphLjxcL3A+XHJcblxyXG48cD5IZSBoYXMgY2VydGFpbiBudW1iZXIgb2YgcG90ZW50aWFsIGxvY2F0aW9ucyBmb3IgdGhlIHJlc3RhdXJhbnRzLCBhbmQgaGUga25vd3MgdGhlIGxvY2F0aW9ucyBvZiB0aGUgc29saXRhaXJzIHdpdGggbG90cyBvZiBwZW9wbGUgd2hpY2ggd2lsbCBvZnRlbiBiZSBoaXMgY3VzdG9tZXJzLjxcL3A+XHJcblxyXG48cD5EZWxpdmVyeSBvZiBlYWNoIHJlc3RhdXJhbnQgd2lsbCBjb3ZlciBhbGwgdGhlIHNvbGl0YWlycyBpbiBnaXZlbiByYWRpdXMuIFBpY2tvIGNhbiBvcGVuIG9ubHkgbGltaXRlZCBudW1iZXIgb2YgcmVzdGF1cmFudHMsIGFuZCBoZSB3YW50cyB0aGF0IHJlc3RhdXJhbnRzIG9uIHRoZSBsb2NhdGlvbnMgd2hpY2ggd2lsbCBjb3ZlciBtYXhpbWFsIG51bWJlciBvZiBwZW9wbGUgaW4gc29saXRhaXJzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGNhbGN1bGF0ZSBtYXhpbWFsIG51bWJlciBvZiBwZW9wbGUgd2hpY2ggd2UgY2FuIGNvdmVyIHdpdGggZGVsaXZlcnkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSB0aGVyZSBhcmUgdHdvIGludGVnZXJzIEsgYW5kIFIsIHNlcGFyYXRlZCB3aXRoIHNwYWNlLCBudW1iZXIgb2YgcmVzdGF1cmFudHMgYW5kIHJhZGl1cyBvZiBkZWxpdmVyeSwgMSAmbGU7IEsgJmxlOyAxMCwgMSAmbGU7IFIgJmxlOyA1MDAuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBzZWNvbmQgbGluZSB0aGVyZSBpcyBpbnRlZ2VyIE0sIG51bWJlciBvZiBsb2NhdGlvbnMsIEsgJmxlOyBNICZsZTsgMjAuPFwvcD5cclxuXHJcbjxwPkluIGVhY2ggb2YgdGhlIG5leHQgTSBsaW5lcyB0aGVyZSBhcmUgdHdvIGludGVnZXIgWCBhbmQgWSwgc2VwYXJhdGVkIHdpdGggc3BhY2UsIGNvb3JkaW5hdGVzIG9mIGVhY2ggbG9jYXRpb24sIC0xMDAwICZsZTsgWCxZICZsZTsgMTAwMC48XC9wPlxyXG5cclxuPHA+SW4gdGhlIG5leHQgbGluZSB0aGVyZSBpcyBpbnRlZ2VyTiwgbnVtYmVyIG9mIHNvbGl0YWlycywgMSAmbGU7IE4gJmxlOyAxMDAuPFwvcD5cclxuXHJcbjxwPkluIGVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyB0aGVyZSBhcmUgdGhyZWUgaW50ZWdlcnMgWCwgWSBhbmQgUywgc2VwYXJhdGVkIHdpdGggc3BhY2UsIFggYW5kIFkgYXJlIGNvb3JkaW5hdGVzIG9mIGVhY2ggc29saXRhaXJlLCBhbmQgUyBpcyBudW1iZXIgb2YgcGVvcGxlIGluIHRoYXQgc29saXRhaXJlLCAtMTAwMCAmbGU7IFgsWSAmbGU7IDEwMDAsIDEgJmxlOyBTICZsZTsgMTAwLiBXZSBjb25zaWRlciB0aGF0IHNvbGl0YWlyZSBpcyBpbiByYWRpdXMgb2Ygc29tZSByZXN0YXVyYW50IGlmIGRpc3RhbmNlIGJldHdlZW4gdGhlbSBpcyBsZXNzIG9yIGVxdWFsIHRvIFIuPFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBubyB0d28gbG9jYXRpb25zIG9mIHJlc3RhdXJhbnRzIG9uIHRoZSBzYW1lIHBsYWNlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIG9ubHkgbGluZSBvZiB0aGUgb3V0cHV0IGZpbGUgd2UgaGF2ZSB0byB3cml0ZSBtYXhpbWFsIG51bWJlciBmcm9tIHRoZSB0ZXh0IGFib3ZlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2003 > Regional Competition - Juniors 3번

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

서버 상태

© 2018 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 대회 개최 문의
사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 강남대로 359 대우도씨에빛2 5층 502호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: [email protected]
통신판매신고번호: 제 2017-서울서초-2193 호

이 사이트는 ACM 또는 ACM-ICPC 대회와 무관하며, ACM으로부터 승인이나 지원을 받지 않고 있습니다.