#P10309. [2023年重庆八中NOI模拟]最佳观影
[2023年重庆八中NOI模拟]最佳观影
题目描述
电影院有 行、每行 个座位, 为奇数。令 。座位 的观影代价为 ,代价越小越好。
最初所有座位均未售出。 个团队依次到来,第 个团队有 人。为该团队选择一行中的 个连续未售座位,使这些座位的观影代价总和最小。若最优选择不唯一,优先选行号较小的,再优先选左端座位编号较小的。
一旦售出,座位就不能再次选择。若没有一组符合要求的座位,则这个团队放弃购票。
输入格式
第一行两个整数 。第二行 个整数 。
输出格式
按团队到来的顺序输出 行。未购票输出 -1,否则输出 ,表示第 行从第 个到第 个座位,含两端。
样例
7 3
1 2 1 2 1 2 1
2 2 2
1 1 2
2 1 1
3 1 2
2 3 3
-1
1 3 3
数据范围
| 测试点 | 上界 | 上界 |
|---|---|---|
| 1–2 | 50 | 25 |
| 3–4 | 200 | 101 |
| 5 | 1000 | 501 |
| 6 | 2000 | 1001 |
| 7 | 50001 | |
| 8 | ||
| 9 | ||
| 10 |