#P3535. [Usaco2014 Open]Fair Photography

    ID: 2745 传统题 1000ms 128MiB 尝试: 214 已通过: 52 难度: 7 上传者: 标签>难度分类提高枚举与搜索全子集枚举排序与序列处理一维前缀和数据结构哈希表CF2200GoldByliyizhen2

[Usaco2014 Open]Fair Photography

[USACO14OPEN] Fair Photography G

题目描述

农夫约翰的 NN 头牛各自站在一条直线围栏的不同位置上。第 ii 头牛站在 xix_i 处,品种编号为 bib_i,共有 88 种品种。

约翰要给连续一段位置上的牛拍照。选定照片的左右端点后,端点及两端之间的牛都必须入镜。照片中必须有至少 KK 个不同品种,而且每个入镜品种的牛数都相同。照片的大小是入镜牛的最右位置与最左位置之差。

请计算满足条件的照片的最大大小。如果没有合格的照片,输出 −1-1。

输入格式

第一行两个整数 N,KN,K。接下来 NN 行,每行两个整数 xi,bix_i,b_i,分别表示一头牛的位置和品种编号。各行可按任意顺序给出。

输出格式

一行一个整数,表示合格照片的最大大小。无解时输出 −1-1。

样例 #1

9 2
1 1
5 1
6 1
9 1
100 1
2 2
7 2
3 3
8 3
6

从位置 22 到 88 拍下的牛中,品种 1,2,31,2,3 各有两头。位置 99 到 100100 之间只有品种 11,达不到 K=2K=2 的要求。

数据范围

1≤N≤1051\le N\le10^5,2≤K≤82\le K\le8,0≤xi≤1090\le x_i\le10^9,1≤bi≤81\le b_i\le8。各 xix_i 两两不同。