A3085 | Kingdom Game II
来源官方 / 2024
时间限制5s
内存限制512MB
通过 / 提交0/0
题目描述
时间限制:5000ms
空间限制 512mb
Yuilice从梦中醒来，发现自己的王国$Yuilice-KingDom$被敌军入侵了，恼怒的Yuilice打开了O神，呼唤他的军团$Zhx$复制人军团支援战场。
现在我们可以将战场视为是一个$N \times N$的二维矩阵，由于Yuilice开启了O神，所以他发现地图上共有$M$支敌军，并且得知第$i$支敌军的位置处于下标为$x_i$与$y_i$的单元格上。
Yuilice一共呼唤了$K$支$Zhx$军团，其中第$i$支军团的初始所在地为$sx_i$与$sy_i$，同时因为传送门太小，导致第$i$支军团到达战场的时间为$t_i$秒。
敌军已经被O神的力量吓破了胆，不会移动。$Zhx$军团在每一秒会划分出四个子军团进行上下左右的移动剿灭敌军，同时被划分出来的子军团还可以继续划分，无穷无尽一直划分下去。
$Zhx$军团神挡杀神佛挡杀佛，所到之处的敌军灰飞烟灭，现在Yuilice困意上头，决定睡个回笼觉，他需要军师--也就是你，算出最少需要几秒才可以消灭所有的敌军？
输入格式
第一行共输入三个整数$n,M,K$ - 代表地图大小与敌军军团数量、$Zhx$军团数量。
随后$M$行，每行输入$2$个整数$x_i$与$y_i$ - 代表第$i$支敌军的所在地。
随后$K$行，每行输入$3$个整数$sx_i、$$sy_i$与$t_i$ - 代表第$i$支$Zhx$军团的所在地与到达时间。
随后$M$行，每行输入$2$个整数$x_i$与$y_i$ - 代表第$i$支敌军的所在地。
随后$K$行，每行输入$3$个整数$sx_i、$$sy_i$与$t_i$ - 代表第$i$支$Zhx$军团的所在地与到达时间。
输出格式
请输出一个整数代表最小需要的秒数。
输入输出样例
输入 #1
5 2 1 1 1 2 2 3 3 0
输出 #1
4
输入 #2
5 2 2 1 1 2 2 1 1 5 3 3 0
输出 #2
4
输入 #3
5 2 2 1 1 2 2 1 1 0 2 2 0
输出 #3
0
【样例解释1】
在第$0$秒时，地图的$[3,3]$降临了一支Zhy军团，在第一秒时分出两个子军团前往$[3,2]$与$[2,3]$,在第二秒时候消灭了位于$[2,2]$的敌军，在第三秒划分出子军团前往$[1,2]$与$[2,1]$，于第四秒时消灭了位于$[1,1]$的敌军。
---
【样例解释2】
位于$[3,3]$降临的军队在第四秒消灭了所有敌军，但是$[1,1]$降临的军队还没有落地。
---
对于$50\%$的数据,$1 \leq n \leq 10 ,1 \leq M,K \leq n - 1, 1 \leq x_i,y_i,sx_i,sy_i \leq n , 0 \leq t_i \leq 10^3$
对于$100\%$的数据,$1 \leq n \leq 5 \times 10^3 ,1 \leq M,K \leq n - 1, 1 \leq x_i,y_i,sx_i,sy_i \leq n , 0 \leq t_i \leq 10^8$
在第$0$秒时，地图的$[3,3]$降临了一支Zhy军团，在第一秒时分出两个子军团前往$[3,2]$与$[2,3]$,在第二秒时候消灭了位于$[2,2]$的敌军，在第三秒划分出子军团前往$[1,2]$与$[2,1]$，于第四秒时消灭了位于$[1,1]$的敌军。
---
【样例解释2】
位于$[3,3]$降临的军队在第四秒消灭了所有敌军，但是$[1,1]$降临的军队还没有落地。
---
对于$50\%$的数据,$1 \leq n \leq 10 ,1 \leq M,K \leq n - 1, 1 \leq x_i,y_i,sx_i,sy_i \leq n , 0 \leq t_i \leq 10^3$
对于$100\%$的数据,$1 \leq n \leq 5 \times 10^3 ,1 \leq M,K \leq n - 1, 1 \leq x_i,y_i,sx_i,sy_i \leq n , 0 \leq t_i \leq 10^8$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？