QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#686372#5417. Chat Programucup-team3474WA 1315ms20992kbC++201.4kb2024-10-29 11:50:042024-10-29 11:50:05

Judging History

你现在查看的是最新测评结果

  • [2024-10-29 11:50:05]
  • 评测
  • 测评结果:WA
  • 用时:1315ms
  • 内存:20992kb
  • [2024-10-29 11:50:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];
ll c,d;
ll ss[N];


bool check(ll mid){
    for(int i=1;i<=n;i++) b[i]=a[i]-mid;
    for(int i=1;i<=n;i++){
        if(b[i]>=0) ss[i]=1;
        else ss[i]=0;
        ss[i]+=ss[i-1];
    }
    ll ad=0;
    for(int i=1;i<=n;i++){
        b[i]+=ad;
        ad+=d;
    }
    // for(int i=1;i<=n;i++) cout<<b[i]<<" ";
    // cout<<endl;
    multiset<PII> se;
    ll minus=-c;
    ll mx=0;
    // cout<<ss[n]<<endl;
    for(int i=1;i<=m;i++) se.insert({b[i],i});
    
    for(int i=1;i+m-1<=n;i++){
        while(se.size()&&((*se.begin()).first-minus)<0) se.erase(se.begin());
        ll tot=se.size();
        tot+=(ss[n]-(ss[i+m-1]-ss[i-1]));
        // cout<<(ss[i+m-1]-s[i-1])<<endl;
        // cout<<i<<" "<<se.size()<<" "<<tot<<endl;
        // if(!se.count({b[i],i})&&b[i]+c>=0) tot++;
        mx=max(mx,tot);
        if(se.count({b[i],i})) se.erase(se.find({b[i],i}));
        se.insert({b[i+m],i+m});
        minus+=d;
    }
    // cout<<mid<<" "<<mx<<" "<<k<<endl;
    return mx>=k;
}

int main(){
    cin>>n>>k>>m;
    cin>>c>>d;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    // check(9);
    ll l=0,r=1e13;
    while(l<r){
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7652kb

input:

6 4 3 1 2
1 1 4 5 1 4

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 10036kb

input:

7 3 2 4 0
1 9 1 9 8 1 0

output:

9

result:

ok 1 number(s): "9"

Test #3:

score: 0
Accepted
time: 0ms
memory: 9816kb

input:

8 3 5 0 0
2 0 2 2 1 2 1 8

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 1315ms
memory: 20496kb

input:

200000 200000 100000 0 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: -100
Wrong Answer
time: 1039ms
memory: 20992kb

input:

200000 1 100000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...

output:

10000000000000

result:

wrong answer 1st numbers differ - expected: '100001000000000', found: '10000000000000'