倾城ファン恋 @ 2018-02-21 17:00:50
```#include <cstring>
```#include <cstdio>
```#include <algorithm>
```#include <cmath>
```#pragma GCC optimize(3)
```using namespace std;
```const int INF=2000000000;
```long long ```n,m,s,w[20005],v[20005],cnt[20005],tmp=I```NF,ans=INF;
```pair<long long,long long>lr[20005];
```long long sum[20005],res=0;
```long long read()
```{
``` long long num=0;
``` char c;
``` c=getchar();
``` while(c<'0'||c>'9')
``` {
``` c=getchar();
``` }
``` while(c>='0'&&c<='9')
``` {
``` num=num*10+c-'0';
``` c=getchar();
``` }
``` return num;
```}
```int pd(long long mid)
```{
```memset(cnt,0,sizeof(cnt));
```memset(sum,0,sizeof(sum));
```res=0;
```for(int i=1;i<=n;i++)
```{
```int oo=w[i]>=mid;
```cnt[i]=cnt[i-1]+oo;
```sum[i]=sum[i-1]+(long long)(oo*v[i]);
``` }
``` for(int i=1;i<=m;i++)
```{
```res+=(cnt[lr[i].second]-```cnt[lr[i].first-1])*(sum[lr[i].second]-```sum[lr[i].first-1]);
```}
```long long kkk=res-s;
``` long long now=abs(kkk);
```if(ans>now)ans=now;
```if(res>=s)
```{
```return 1;
```}
```return 0;
```}
```int main()
```{
``` n=read(),m=read(),s=read();
```for(int i=1;i<=n;i++)
```{
```w[i]=read(),v[i]=read();
```}
```long long l,r;
```for(int i=1;i<=m;i++)
```{
```l=read(),r=read();
```lr[i]=make_pair(l,r);
```}
```l=0,r=tmp;
```while(l<=r)
```{
```long long mid=(l+r)/2;
```if(pd(mid)!=0)
```{
vl=mid+1;
```}
```else
```{
```r=mid-1;
```}
```}
```cout<<ans<<endl;
```return 0;
```}
by 倾城ファン恋 @ 2018-02-21 17:02:15
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#pragma GCC optimize(3)
using namespace std;
const int INF=2000000000;
long long n,m,s,w[20005],v[20005],cnt[20005],tmp=INF,ans=INF;
pair<long long,long long>lr[20005];
long long sum[20005],res=0;
long long read()
{
long long num=0;
char c;
c=getchar();
while(c<'0'||c>'9')
{
c=getchar();
}
while(c>='0'&&c<='9')
{
num=num*10+c-'0';
c=getchar();
}
return num;
}
int pd(long long mid)
{
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
res=0;
for(int i=1;i<=n;i++)
{
int oo=w[i]>=mid;
cnt[i]=cnt[i-1]+oo;
sum[i]=sum[i-1]+(long long)(oo*v[i]);
}
for(int i=1;i<=m;i++)
{
res+=(cnt[lr[i].second]-cnt[lr[i].first-1])*(sum[lr[i].second]-sum[lr[i].first-1]);
}
long long kkk=res-s;
long long now=abs(kkk);
if(ans>now)ans=now;
if(res>=s)
{
return 1;
}
return 0;
}
int main()
{
n=read(),m=read(),s=read();
for(int i=1;i<=n;i++)
{
w[i]=read(),v[i]=read();
}
long long l,r;
for(int i=1;i<=m;i++)
{
l=read(),r=read();
lr[i]=make_pair(l,r);
}
l=0,r=tmp;
while(l<=r)
{
long long mid=(l+r)/2;
if(pd(mid)!=0)
{
l=mid+1;
}
else
{
r=mid-1;
}
}
cout<<ans<<endl;
return 0;
}
by 渺小的Mastar @ 2019-04-05 04:09:57
你的INF要取9223372036854775807