专栏首页饶文津的专栏【Codeforces 738C】Road to Cinema

【Codeforces 738C】Road to Cinema

http://codeforces.com/contest/738/problem/C

Vasya is currently at a car rental service, and he wants to reach cinema. The film he has bought a ticket for starts in t minutes. There is a straight road of length s from the service to the cinema. Let's introduce a coordinate system so that the car rental service is at the point 0, and the cinema is at the point s.

There are k gas stations along the road, and at each of them you can fill a car with any amount of fuel for free! Consider that this operation doesn't take any time, i.e. is carried out instantly.

There are n cars in the rental service, i-th of them is characterized with two integers ci and vi — the price of this car rent and the capacity of its fuel tank in liters. It's not allowed to fuel a car with more fuel than its tank capacity vi. All cars are completely fueled at the car rental service.

Each of the cars can be driven in one of two speed modes: normal or accelerated. In the normal mode a car covers 1 kilometer in 2 minutes, and consumes 1 liter of fuel. In the accelerated mode a car covers 1 kilometer in 1 minutes, but consumes 2 liters of fuel. The driving mode can be changed at any moment and any number of times.

Your task is to choose a car with minimum price such that Vasya can reach the cinema before the show starts, i.e. not later than in t minutes. Assume that all cars are completely fueled initially.

Input

The first line contains four positive integers nks and t (1 ≤ n ≤ 2·105, 1 ≤ k ≤ 2·105, 2 ≤ s ≤ 109, 1 ≤ t ≤ 2·109) — the number of cars at the car rental service, the number of gas stations along the road, the length of the road and the time in which the film starts.

Each of the next n lines contains two positive integers ci and vi (1 ≤ ci, vi ≤ 109) — the price of the i-th car and its fuel tank capacity.

The next line contains k distinct integers g1, g2, ..., gk (1 ≤ gi ≤ s - 1) — the positions of the gas stations on the road in arbitrary order.

Output

Print the minimum rent price of an appropriate car, i.e. such car that Vasya will be able to reach the cinema before the film starts (not later than in t minutes). If there is no appropriate car, print -1.

Examples

input

3 1 8 10
10 8
5 7
11 9
3

output

10

input

2 2 10 18
10 4
20 6
5 3

output

20

Note

In the first sample, Vasya can reach the cinema in time using the first or the third cars, but it would be cheaper to choose the first one. Its price is equal to 10, and the capacity of its fuel tank is 8. Then Vasya can drive to the first gas station in the accelerated mode in 3 minutes, spending 6 liters of fuel. After that he can full the tank and cover 2 kilometers in the normal mode in 4 minutes, speding 2 liters of fuel. Finally, he drives in the accelerated mode covering the remaining 3 kilometers in 3 minutes and spending 6 liters of fuel.

题意:n个价格c[i],油量v[i]的汽车,求最便宜的一辆使得能在t时间内到达s,路途中有k个位置在g[i]的加油站,可以免费加满油,且不耗时间。每辆车有两种运行模式可以随时切换:1.每米一分钟两升油;2.每米两分钟一升油。

题解:二分求可以到达s的最小油量。对于油量v,能到达s的条件是:油量足够经过最长路程(中途不能加油);总的最小时间不超过t。为了求最小时间,可以用线性规划:一段不加油的路程长度为l,假设x米运行的是1.模式,则l-x米运行的是2.模式。总时间为t。则有

\begin{equation} \left\{ \begin{aligned} t=x+2*(l-x)\\ v≥x*2+l-x\\ x≥0\\ l-x≥0\\ \end{aligned} \right. \end{equation} 

化简一下:

\begin{equation} \left\{ \begin{aligned} t=2*l-x\\ x≤v-l\\ l≥x≥0\\ \end{aligned} \right. \end{equation}

最后得到:

\begin{aligned} t_{min} & = 2*l-x_{max}\\ & = 2*l-min(v-l,l)\\ & = max(l*3-v,l)\\ \end{aligned}

且v≥l,可以改为v≥max(l)。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 200005
using  namespace std;
int n,k,s,t,c[N],v[N],g[N],mg,ans=1e9+1,mv;
bool ck(int v){
    if(v<mg)return 0;
    int tol=0;
    for(int i=1;i<=k+1;i++){
        tol+=max(g[i],3*g[i]-v);
        if(tol>t)return 0;
    }
    return 1;
}
int main(){
    scanf("%d%d%d%d",&n,&k,&s,&t);
    for(int i=1;i<=n;i++)
        scanf("%d%d",c+i,v+i);
    for(int i=1;i<=k;i++)
        scanf("%d",g+i);
    sort(g+1,g+1+k);
    g[k+1]=s;
    for(int i=k+1;i;i--)
        mg=max(mg,g[i]-=g[i-1]);
//接下来是萌萌哒的二分
    for(int l=0,r=1e9,m=l+r>>1;l<=r;ck(m=l+r>>1)?r=m-1,mv=m:l=m+1);
    if(mv)
    for(int i=1;i<=n;i++)if(v[i]>=mv) ans=min(ans,c[i]);
    if(ans>1e9)ans=-1;
    printf("%d",ans);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【CodeForces 567E】President and Roads(最短路)

    Berland has n cities, the capital is located in city s, and the historic home to...

    饶文津
  • 【CodeForces 489A】SwapSort

    In this problem your goal is to sort an array consisting of n integers in at mos...

    饶文津
  • 【UVALive 3905】BUPT 2015 newbie practice #2 div2-D-3905 - Meteor

    http://acm.hust.edu.cn/vjudge/contest/view.action?cid=102419#problem/D

    饶文津
  • DAY83:阅读Compute Capability 7.x

    我们正带领大家开始阅读英文的《CUDA C Programming Guide》,今天是第83天,我们正在讲解计算能力,希望在接下来的17天里,您可以学习到原汁...

    GPUS Lady
  • 图片语义级属性轻松改变

    论文: Deep Feature Interpolation for Image Content Changes

    用户1908973
  • IBM刀片服务器管理模块恢复出厂默认值实战

    Resetting the management module back to factory defaults

    力哥聊运维与云计算
  • 与异构服务器在线联合布置和分配虚拟网络功能(Networking and Internet Architecture)

    网络功能虚拟化(NFV)是一种新兴的虚拟化技术,具有显著降低成本和提高服务敏捷性的潜力。网络功能虚拟化使因特网服务提供商(isp)能够在不安装新设备的情况下使用...

    用户6869393
  • 【SAP FICO系列】SAP ABAP的替代和校验

    I. Creating, activating and transporting validations and substitutions 1. Whic...

    matinal
  • 人类追寻在艺术中发现数学美 (CS CY)

    用20世纪英国数学家G.H.Hardy的话说,“人类的功能是发现或观察数学”(1)。数个世纪以来,从古埃及开始,人类为美狩猎,被艺术和自然约束。这个对数学美的需...

    木樾233
  • 【PAT甲级】World Cup Betting

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk

扫码关注云+社区

领取腾讯云代金券