시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 105 | 40 | 35 | 36.842% |
果物好きのビ太郎は,いちごのつかみ取りに挑戦することにした.ビ太郎の目の前には 1 脚の机がある.机は長方形の形をしており,縦 H 行,横 W 列のマス目状に区切られている.机には N 個のいちごが置かれており,i 番目 (1 ≦ i ≦ N) のいちごは上から Ai 行目,左から Bi 列目のマスにある.複数のいちごが同じマスに置かれている可能性もある.
ビ太郎は机から,縦 3 行,横 3 列の正方形の領域をなす 9 個のマスを選び,それらのマスにあるいちごをすべて取る.この動作は 1 回だけ行う.
ビ太郎は,なるべく多くのいちごを取りたい.
机の大きさといちごの位置についての情報が与えられたとき,取れるいちごの個数の最大値を求めるプログラムを作成せよ.
入力は以下の形式で標準入力から与えられる.
H W N A1 B1 A2 B2 : AN BN
標準出力に,取れるいちごの個数の最大値を 1 行で出力せよ.
번호 | 배점 | 제한 |
---|---|---|
1 | 14 | H ≦ 1 000,W ≦ 1 000,N ≦ 20. |
2 | 16 | H ≦ 1 000,W ≦ 1 000. |
3 | 29 | H ≦ 1 000 000,N ≦ 500. |
4 | 15 | H = 3. |
5 | 20 | H ≦ 1 000 000. |
6 | 6 | 追加の制約はない. |
4 5 7 1 1 1 5 2 2 2 4 3 3 4 2 4 4
5
いちごの配置は図のようになっている (赤い丸がいちごを表す).
太枠で囲った領域をなすマスを選ぶことで,5 個のいちごが取れる.
5 個よりも多くのいちごを取ることはできないので,5 を出力する.
この入力例は小課題 1, 2, 3, 5, 6 の制約を満たす.
3 5 6 1 1 1 2 2 1 2 4 2 4 3 4
4
複数のいちごが同じマスに置かれていることもある.
この入力例はすべての小課題の制約を満たす.
3 99999 9 1 77813 2 77813 3 77813 1 77814 2 77814 3 77814 1 77815 2 77815 3 77815
9
この入力例は小課題 3, 4, 5, 6 の制約を満たす.
11 11 20 7 7 6 11 5 7 8 8 9 9 5 5 8 4 4 4 4 8 2 6 1 6 6 2 3 3 9 3 7 5 6 1 10 6 6 10 11 6 3 9
4
この入力例は小課題 1, 2, 3, 5, 6 の制約を満たす.
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics for Girls > JOIG 2021/2022 4번