[POI 2023/2024 R1] Budowa lotniska

Luogu
IDLGP9921
Time500ms
Memory128MB
DifficultyP5
POI(波兰)2023前缀和分类讨论
给你一个 $n\times n$ 的地图,地图上有 `.` 有 `X`。 求出最大的 $k$,使得: 在地图上能找到 $m(m\leq 2)$ 个 $1\times k$ 或 $k\times 1$ 的长条,使得长条不交且长条内全是 `.`。 ## Input 第一行两个正整数 $n,m$。 接下来 $n$ 行,描述地图。 ## Output 一行一个非负整数,最大的 $k$。 [samples] ## Background 译自 [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/)。 ## Note 样例解释: ```plain .X... .XXXX XX..2 111.2 .X.X2 ``` 对于所有数据,$1\leq n\leq1500$,$1\leq m\leq2$,地图上只有 `.` 和 `X`。 | 子任务编号 | 附加限制 | 分值 | | :----------: | :----------: | :----------: | | 1 | $m=1$ | 20 | | 2 | $n\leq 30$ | 22 | | 3 | $n\leq 300$ | 23 | | 4 | | 35 |
Samples
Input #1
5 2
.X...
.XXXX
XX...
.....
.X.X.
Output #1
3
Input #2
2 1
..
..
Output #2
2
Input #3
2 2
X.
..
Output #3
1
Input #4
10 2
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
..........
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
Output #4
5
Input #5
10 2
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
Output #5
10
Input #6
见附件
Output #6
531
API Response (JSON)
{
  "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[...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments