#P3807. Neerc2011 Lanes

    ID: 3009 传统题 1000ms 64MiB 尝试: 9 已通过: 3 难度: 8 上传者: 标签>CF2400提高+/省选-贡献法增量维护栈同向双指针等差数列求和

Neerc2011 Lanes

题目描述

某座大桥上有 n1n_1 条从左至右的车道,n2n_2 条从右至左的车道,还有一条潮汐车道。在早上从左向右行驶的车辆较多,潮汐车道的方向是从左向右;晚上正好相反。 也就是说早上 n1+1n_1+1 条左右车道,n2n_2 条右左车道;晚 上有 n1n_1 条左右车道,n2+1n_2+1 条右左车道。

交通是很复杂的问题,我们有如下的抽象模型: 从早到晚被分为 mm 个离散的时刻,编号从 11 开始。 在每个时刻,两侧均有一些车抵达。 设左右车道和右左车道各有 L,RL,R 条车道,那么左侧最多通行 LL 辆车,右侧最多通行 RR 辆车。每个时段先计入新到的车辆,再让车辆通行。 剩下的车等待下一时刻。 如果在时刻 mm 后仍有车辆在等待,那么后面的时刻仍按同样模型进行,只是不会有新到达的车辆了。

你的任务是决定在哪一时刻改变潮汐车道的方向,能使所有车辆等待时间的总和最小化。

不过潮汐车道也不是瞬间就能改变方向的,它需要 rr 个时刻来改变方向。也就是说,如果在 tt 时刻改变方向,那么在 [t,t+r−1][t,t+r-1] 时刻内潮汐车道不能使用,即左右和右左车道各有 n1n_1 和 n2n_2 条。自时刻 t+rt+r 起,潮汐车道供从右向左的车辆使用。

输入格式

第一行四个整数 n1,n2,m,rn_1,n_2,m,r。

接下来 mm 行,第 i+1i+1 行两个整数 a,ba,b 表示在 ii 时刻有 aa 辆车从左侧抵达,bb 辆车从右侧抵达。

输出格式

输出一个整数 tt(1≤t≤m1\le t\le m),表示使总等待时间最小的换向时刻。若有多个最优时刻,输出最早的一个。

2 2 10 2
1 0
2 1
3 2
4 2
3 3
2 3
1 5
0 3
1 2
0 1
4

数据规模与约定

对于 100%100\% 的数据,1≤n1,n2≤101\leq n_1,n_2\leq 10,1≤m≤1051\le m\le10^5,1≤r≤m1\le r\le m。每个时刻两侧各有 00 至 100100 辆车到达。

题目来源