QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#686372 | #5417. Chat Program | ucup-team3474 | WA | 1315ms | 20992kb | C++20 | 1.4kb | 2024-10-29 11:50:04 | 2024-10-29 11:50:05 |
Judging History
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'