QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #693328 | #9331. Maximize the Minimum | lytqwq# | WA | 51ms | 8028kb | C++14 | 2.3kb | 2024-10-31 15:58:27 | 2024-10-31 15:58:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define ll long long
#define INF 0x7fffffffffffffffLL
int read(){
int res=0,zf=1;char ch;
while((ch=getchar())<48||ch>57)if(ch=='-')zf=!zf;res=(ch^48);
while((ch=getchar())>=48&&ch<=57)res=(res<<3)+(res<<1)+(ch^48);
return zf?res:(-res);
}
ll readll(){
ll res=0;int zf=1;char ch;
while((ch=getchar())<48||ch>57)if(ch=='-')zf=!zf;res=(ch^48);
while((ch=getchar())>=48&&ch<=57)res=(res<<3)+(res<<1)+(ch^48);
return zf?res:(-res);
}
int n,m;
ll maxs,adds;
struct node{
ll s,w;int from;
}s[N<<1];
ll sa[N],sb[N],sap[N],sbp[N];
inline bool operator <(const node&x,const node&y){return x.s<y.s;}
int chk(ll d){
int lst=0;
for(int i=0;i<=n+m;i++)sap[i]=sbp[i]=-INF;
for(int i=1;i<=n+m;i++){
if(lst<i-1&&s[lst+1].s+d<=s[i].s)lst++;
if(s[i].from){
sb[i]=max(sb[i-1]+s[i].w,sa[lst]+s[i].w);
sa[i]=sa[i-1];
if(sa[lst]>0)sbp[i]=max(sbp[i-1]+s[i].w,sa[lst]+s[i].w);
else sbp[i]=sbp[i-1]+s[i].w;
sap[i]=sap[i-1];
}else{
sa[i]=max(sa[i-1]+s[i].w,sb[lst]+s[i].w);
sb[i]=sb[i-1];
if(sb[lst]>0)sap[i]=max(sap[i-1]+s[i].w,sb[lst]+s[i].w);
else sbp[i]=sbp[i-1]+s[i].w;
sbp[i]=sbp[i-1];
}
}
return max(sap[n+m],sbp[n+m])>=adds-maxs;
}
int main(){
int t=read();
while(t--){
n=read();m=read();maxs=readll();
adds=0;
for(int i=1;i<=n;i++){
s[i].s=readll();
s[i].from=0;
//adds+=s[i].s;
}
for(int i=1;i<=m;i++){
s[i+n].s=readll();
s[i+n].from=1;
// adds+=s[i+n].s;
}
for(int i=1;i<=n;i++){
s[i].w=readll();
adds+=s[i].w;
}
for(int i=1;i<=m;i++){
s[i+n].w=readll();
adds+=s[i+n].w;
}
if(adds<maxs)maxs=adds;
sort(s+1,s+n+m+1);
ll L=0,R=2e10,res=0;
while(L<=R){
ll mid=(L+R)>>1;
if(chk(mid)){
res=mid;
L=mid+1;
}else{
R=mid-1;
}
}
printf("%lld\n",res);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8028kb
input:
2 1 4 10 15 1 6 9 13 8 3 1 2 4 5 4 4 -1 5 3 2 -4 -7 8 6 2 2 3 1 1 2 3 1 1 1
output:
14 3
result:
ok 2 number(s): "14 3"
Test #2:
score: -100
Wrong Answer
time: 51ms
memory: 7996kb
input:
40000 5 3 4 1 -5 -2 -5 4 -3 -4 -4 4 8 2 4 7 5 3 7 5 3 6 -4 -7 -4 -1 -7 -4 -4 -2 6 8 3 4 5 5 3 5 5 3 6 -1 2 3 -4 -1 -1 -2 -3 8 3 4 3 2 2 5 2 5 3 4 -5 -2 3 -1 2 -3 0 -2 6 5 1 1 6 7 8 7 5 3 4 0 0 1 -4 -2 -4 -4 -3 7 7 5 8 3 8 2 4 5 3 4 0 -4 -1 1 -6 -2 -5 -4 7 4 5 7 3 5 5 2 5 3 6 -4 -3 0 2 -4 -5 -4 -4 6 ...
output:
0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 1 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 3 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 2 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 ...
result:
wrong answer 1st numbers differ - expected: '1', found: '0'