{"problem":{"name":"[POI 2023/2024 R1] Budowa lotniska","description":{"content":"给你一个 $n\\times n$ 的地图，地图上有 `.` 有 `X`。 求出最大的 $k$，使得： 在地图上能找到 $m(m\\leq 2)$ 个 $1\\times k$ 或 $k\\times 1$ 的长条，使得长条不交且长条内全是 `.`。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":131072},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9921"},"statements":[{"statement_type":"Markdown","content":"给你一个 $n\\times n$ 的地图，地图上有 `.` 有 `X`。\n\n求出最大的 $k$，使得：\n\n在地图上能找到 $m(m\\leq 2)$ 个 $1\\times k$ 或 $k\\times 1$ 的长条，使得长条不交且长条内全是 `.`。\n\n## Input\n\n第一行两个正整数 $n,m$。\n\n接下来 $n$ 行，描述地图。\n\n## Output\n\n一行一个非负整数，最大的 $k$。\n\n[samples]\n\n## Background\n\n译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Budowa lotniska](https://sio2.mimuw.edu.pl/c/oi31-1/p/bud/)。\n\n## Note\n\n样例解释：\n\n```plain\n.X...\n.XXXX\nXX..2\n111.2\n.X.X2\n```\n\n对于所有数据，$1\\leq n\\leq1500$，$1\\leq m\\leq2$，地图上只有 `.` 和 `X`。\n\n| 子任务编号 | 附加限制 | 分值 |\n| :----------: | :----------: | :----------: |\n| 1 | $m=1$ | 20 |\n| 2 | $n\\leq 30$ | 22 |\n| 3 | $n\\leq 300$ | 23 |\n| 4 |  | 35 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9921","tags":["POI（波兰）","2023","前缀和","分类讨论"],"sample_group":[["5 2\n.X...\n.XXXX\nXX...\n.....\n.X.X.\n","3\n"],["2 1\n..\n..\n","2\n"],["2 2\nX.\n..\n","1\n"],["10 2\nXXXXXXXXXX\nXXXXXXXXXX\nXXXXXXXXXX\nXXXXXXXXXX\nXXXXXXXXXX\n..........\nXXXXXXXXXX\nXXXXXXXXXX\nXXXXXXXXXX\nXXXXXXXXXX\n","5\n"],["10 2\nXX.XXXXX.X\nXX.XXXXX.X\nXX.XXXXX.X\nXX.XXXXX.X\nXX.XXXXX.X\nXX.XXXXX.X\nXX.XXXXX.X\nXX.XXXXX.X\nXX.XXXXX.X\nXX.XXXXX.X\n","10\n"],["见附件","531\n"]],"created_at":"2026-03-03 11:09:25"}}