为什么65分?嗷呜。。

P1314 [NOIP2011 提高组] 聪明的质监员

倾城ファン恋 @ 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


|