A174979.彩带对齐

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:256MB

题目描述

一条长彩带由 nn 个等大的方格组成,另一条短彩带由 mm 个等大的方格组成。两条彩带的方格都从左到右编号,从 11 开始。每个方格有一个颜色编号,颜色编号相同表示颜色相同。

保持短彩带的方向不变,把它放在长彩带上,使短彩带的每个方格都正好覆盖长彩带的一个方格。短彩带必须完全落在长彩带内。

设短彩带的第 11 格覆盖长彩带的第 ss 格,则称 ss 为这次摆放的起点。此时短彩带的第 jj 格覆盖长彩带的第 s+j−1s+j-1 格。每对颜色相同的覆盖方格得到 11 分,颜色不同不得分。

请输出一次摆放能得到的最高分,以及有多少个不同起点能得到这个最高分。起点不同就视为不同摆放。

输入格式

第一行包含两个整数 n,mn,m,分别表示长彩带和短彩带的方格数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 aia_i 表示长彩带第 ii 格的颜色编号。

第三行包含 mm 个整数 b1,b2,…,bmb_1,b_2,\ldots,b_m,其中 bjb_j 表示短彩带第 jj 格的颜色编号。

输出格式

输出一行两个整数,依次表示最高分和达到最高分的不同起点数量,用一个空格隔开。

输入输出样例

  • 输入#1

    6 3
    1 2 1 2 1 3
    1 2 1
    

    输出#1

    3 2
    
  • 输入#2

    5 2
    4 4 7 4 7
    4 7
    

    输出#2

    2 2
    

说明/提示

样例 #1 解释

短彩带有 33 格,合法起点为 1,2,3,41,2,3,4。

起点 被覆盖的长彩带颜色 得分
1 1 2 1 3
2 2 1 2 0
3 1 2 1 3
4 2 1 3 0

最高分为 33,起点 11 和 33 都能达到,共有 22 个。

数据范围

对于所有测试数据,满足:

  • 1≤m≤n≤3001 \le m \le n \le 300;
  • 1≤ai,bj≤1091 \le a_i,b_j \le 10^9。

输入解题思路,AI测评打分。不知道怎么写?

首页