bzoj#P1136. [POI2009]Arc
[POI2009]Arc
题目描述
给定一个序列 和一个整数 ,求出 的一个长度为 的子序列 满足:
- 。
- 在满足 (1) 的情况下 字典序最大。
输入格式
第一行一个数 ,以下一行,为序列 。以一个单独的 结束。
输出格式
行,每行一个数,其中第 行为 。
12
5 8 3 15 8 0
12
15
8
数据规模与约定
$1 \le a_i \le 10^9,k \le n \le 1.5 \times 10^7,k \le 10^6$.
提示
按照这里:http://main.edu.pl/en/archive/oi/16/arc 来写交互式的程序,然后把这个东西:http://oi.edu.pl/static/attachment/20110704/oi16-etap2-arc.zip 解压后把 etap2/arc/prog
里的 carclib.c
的内容贴到自己的源码中的一大堆“include”之前。这样这个程序就从交互式 程序变成普通的程序了,就可以AC了。
鸣谢 vfleaking。