0分求调
查看原帖
0分求调
902073
Zipao楼主2023/9/12 15:24
#include<bits/stdc++.h>
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define re register
#define int long long
#define dfor(i,a,b) for(re int i=a;i<=b;++i)
#define dforr(i,a,b) for(re int i=a;i>=b;--i)
#define dforn(i,a,b) for(re int i=a;i<=b;++i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define INF 0x7fffffff
#define tt(x) cout<<x<<'\n'
#define ls i<<1
#define rs i<<1|1
#define lowbit(x) (x&-x)
using namespace std;
typedef unsigned int ull;
const int N=1e5+10,M=4e6+10,mod=19650827;
int read(void)
{
    re int x=0,f=1;re char c=get();
    while(!is(c)) { if(c==45) f=-1; c=get();}
    while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();
    return x*f;
}
void write(int x)
{
    if(x<0) x=-x,put(45);
    if(x>9) write(x/10);
    put((x%10)^48);
}
int n,m,l,r,k,sum,a[N];
priority_queue<int,vector<int>,greater<int> >q;
vector<int> v;
bool check(int mid)
{
    re int cnt=sum;
    vector<int> t;
    dfor(i,0,v.size()-1) t.push_back(v[i]);
    dfor(i,0,v.size()-1)
        if(mid>t[i]) cnt=cnt-t[i]+mid,t[i]=mid;//t=v,如果mid大于t[i]我们就可以做替换以求sum最大
    if(cnt<=r)
    {
        dfor(i,0,v.size()-1) v[i]=t[i];//有可能mid过大超过r,所以让被赋值的t先尝试,如果不超过r再让v=t
        sum=cnt;
        return 1;
    }
    return 0;
}
signed main()
{
    n=read(),m=read(),k=read(),l=read(),r=read();
    re int kep=0;
    dfor(i,1,n) a[i]=read();
    a[m]=0;//a[m]=0,该值对sum的贡献最小
    dfor(i,1,n)
    {
        if(i<=k)
        {
            kep+=a[i],q.push(a[i]);
            if(i==k) sum+=kep,v.push_back(q.top());
        }
        else
        {
            if(a[i]>q.top())
            {
                kep=kep-q.top()+a[i];
                q.pop(),q.push(a[i]);
            }
            sum+=kep,v.push_back(q.top());//v记录a[m]应该与何值做比较,因为a[m]=0上,所以此时a[m]应与最小值比较,所以记录最小值
        }
    }
    if(sum>r)//贡献最小还是>r就一定-1
    {
        write(-1);
        return 0;
    }
    re int ll=1,rr=r;
    while(ll<rr)//二份答案求最大
    {
        int mid=(ll+rr+1)>>1;
        if(check(mid)) ll=mid;
        else rr=mid-1;
    }
    if(sum<l) write(-1);
    else write(sum);
    return 0;
}
2023/9/12 15:24
加载中...