序列
题目描述
给定序列 a1,…,an,以及参数 X,A。选择一个子序列,其下标依次为 1≤p1<p2<⋯<pk≤n。若对每个 i=1,2,…,n 都有
A−iX+j:pj≤i∑(apj+X)≥0,
则称这个子序列为优秀的。
等价地,从数值 A 开始,依次处理每个位置:选入的位置加上 ai,未选入的位置减去 X;每处理完一个位置,当前数值必须非负。
给定分段端点 b0=0<b1<⋯<bm=n 和阈值 hi。记第 i 段未选入的位置数为
ci=bi−bi−1−#{j:bi−1<pj≤bi}.
优秀子序列的价值是满足 ci≥hi 的段数,即
i=1∑m[ci≥hi].
其中方括号表示条件成立取 1,否则取 0。求价值最大的优秀子序列。
输入格式
第一行四个整数 n,m,X,A。
第二行 n 个整数 a1,…,an。
接下来 m 行,第 i 行两个整数 bi,hi。
输出格式
第一行输出最大价值。
第二行输出所选子序列长度 k。
第三行输出递增的下标 p1,…,pk;k=0 时输出空行。若有多个方案,输出任意一个。
若第一行正确且输出格式正确,可以获得 40% 的分数。
样例输入
5 3 3 3
7 1 0 1 2
1 1
3 1
5 2
样例输出
2
2
1 2
样例说明
选择位置 1,2,三段未选入的位置数依次为 0,1,2,故价值为 0+1+1=2。
数据范围
- 测试点 1、2:n≤20。
- 测试点 3、4:n≤100,X,ai≤10。
- 测试点 5:所有 ai 相等。
- 测试点 6:n≤500,m≤18。
- 测试点 7、8:n≤500。
- 对于全部数据,1≤n≤50000,1≤m≤50,0≤ai,X,A≤10000,bi<bi+1,bm=n。