HAPPY_END @ 2018-10-20 01:20:35

by HAPPY_END @ 2018-10-20 01:27:27

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 200000
#define MAXM 200000
struct node
{
    int v,w,num;
}p[MAXN+1];
long long y[MAXN+1],s,now_v[MAXM+1],now_num[MAXM+1],n,m,L[MAXM+1],R[MAXM+1],flag,ans;
bool cmp(node a,node b)
{
    return a.w>b.w;
}
int main()
{
    freopen("qc.in","r",stdin);
    freopen("qc.out","w",stdout);
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].w>>p[i].v;
        p[i].num=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>L[i]>>R[i];
    }
    sort(p+1,p+n+1,cmp);
    ans=s;
    for(int W=1;W<=n;W++)
    {
        flag=0;
        if(p[W].w==p[W+1].w)flag=1;
        y[W]=y[W-1];
        for(int i=1;i<=m;i++)
            if(p[W].num<=R[i]&&p[W].num>=L[i])
            {
                y[W]+=now_v[i]+now_num[i]*p[W].v+p[W].v;
                now_num[i]=now_num[i]+1;
                now_v[i]=now_v[i]+p[W].v; 
            }
        if(!flag&&ans>y[W]-s&&ans>s-y[W])ans=max(y[W]-s,s-y[W]);
        if(y[W]>s)break;
    }
    cout<<ans<<endl;
    system("pause");
    return 0;
}

by HAPPY_END @ 2018-10-20 01:28:41

自己想的奇怪动规，望不喷

by ShineEternal @ 2018-10-20 06:27:46

@HAPPY_END 同志你真刻苦