← 返回题目列表

AtCoder · joi2025ho_a

A. 着色(网格着色)

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

K总裁正在设计一种由网格代表的图案, N 行和 N 列。为了实现这一目标,他决定用整数代表的颜色绘制每个单元格。让我们参考一下单元格中的 i- 第行 (1 \leq i \leq N)和 j- 第列 (1 \leq j \leq N) 作为单元格 (i,j).

目前,第一列和第一行中的单元格已绘制。具体来说,细胞 (i,1) (1 \leq i \leq N) 涂有颜色 A_i 和细胞 (1,j) (1 \leq j \leq N) 涂有颜色 B_j。请注意 A_1 = B_1.

对于剩下的未涂漆的单元格,K总统将按照以下程序对它们进行涂漆:

  • 对于每个 i=2,3,\dots,N 按顺序绘制单元格 i第行如下:
    • 对于每个 j=2,3,\dots,N 按顺序,绘制单元格 (i,j) 与以下之间数字较大的颜色:
      • 单元格的颜色 (i-1,j),和
      • 单元格的颜色 (i,j-1).
      如果两种颜色具有相同的数字,则用该颜色绘制单元格。

K 总统想确定最多的单元格上涂的颜色 N^2 单元格已被涂色,以及涂有该颜色的单元格数量。

编写一个程序,根据网格的大小以及第一列和第一行的颜色信息,确定在最大数量的单元格上绘制的颜色编号以及用该颜色绘制的单元格的数量。如果在最大数量的单元格上绘制多种颜色,则输出 最大色号 其中。


输入

从标准输入读取以下数据。

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N

输出

将一行写入标准输出,其中包含两个以空格分隔的整数:

  1. 在最大数量的单元格上绘制的颜色编号,以及
  2. 用该颜色绘制的单元格数量。

如果在最多数量的单元格上绘制多种颜色,则输出其中最大的颜色数。


约束

  • 2 \leq N \leq 200\,000.
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N).
  • 1 \leq B_j \leq 10^9 (1 \leq j \leq N).
  • A_1 = B_1.
  • 给定值均为整数。

子任务

  1. (15 点) N \leq 500, A_i \leq 100\,000 (1 \leq i \leq N), B_j \leq 100\,000 (1 \leq j \leq N).
  2. (10 点) N \leq 500.
  3. (20 点) A_i \leq 2 (1 \leq i \leq N), B_j \leq 2 (1 \leq j \leq N).
  4. (25 点) A_i < A_{i+1} (1 \leq i \leq N-1), B_j < B_{j+1} (1 \leq j \leq N-1).
  5. (30 点)没有额外的限制。

示例输入 1

3
5 2 5
5 3 1

示例输出 1

5 4

在此示例中,网格中每个单元格的颜色如下:

5 3 1
2 3 3
5 5 5

最大数量的单元格上绘制的颜色编号是 5,出现在 4 细胞。因此,打印 5 和 4 按此顺序,用空格分隔。

此示例输入满足子任务的约束 1, 2,和 5.


示例输入 2

3
1 7 8
1 3 5

示例输出 2

8 3

在此示例中,网格中每个单元格的颜色如下:

1 3 5
7 7 7
8 8 8

最大数量的单元格上绘制的颜色数字是 7 和 8,每个都画在 3 细胞。在这种情况下,输出较大的颜色数, 8,后跟单元格数量, 3,用空格分隔。

此示例输入满足子任务的约束 1, 2, 4,和 5.


示例输入 3

4
2 1 2 1
2 1 1 2

示例输出 3

2 10

此示例输入满足子任务的约束 1, 2, 3,和 5.