QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353203 | #8057. Best Carry Player 4 | ucup-team134# | WA | 62ms | 3904kb | C++17 | 1.4kb | 2024-03-13 23:10:29 | 2024-03-13 23:10:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=500050;
int p[N];
ll a[N],b[N];
const ll inf=1e16;
int Find(int x){return p[x]==x?x:p[x]=Find(p[x]);}
bool was[N];
int main(){
int t;
scanf("%i",&t);
while(t--){
int m;
scanf("%i",&m);
for(int i=0;i<=m;i++)p[i]=i,was[i]=false;
for(int i=0;i<m;i++){
scanf("%lld",&a[i]);
//if(i==0)a[i]=inf;
if(a[i]==0)p[i]=i+1;
}
ll ans=0;
bool large=false;
for(int i=0;i<m;i++){
scanf("%lld",&b[i]);
//if(i==0)b[i]=inf;
while(b[i]>0){
int j=Find(m-1-i);
if(j==m)break;
ll take=min(a[j],b[i]);
b[i]-=take;
a[j]-=take;
ans+=take;
if(i+j>=m)large=true;
was[i]=true;
if(a[j]==0)p[j]=j+1;
}
}
bool A0=true,B0=true;
for(int i=0;i<m;i++){
if(a[i]!=0)A0=false;
if(b[i]!=0)B0=false;
}
if(A0){
ans+=b[m-1];
b[m-1]=0;
}
if(B0){
ans+=a[m-1];
a[m-1]=0;
}
if(large||ans==0)printf("%lld\n",ans);
else{
int mn=m,mx=-1;
for(int i=0;i<m;i++){
if(was[i]){
mn=min(mn,i);
mx=max(mx,i);
}
}
bool ok1=false;
bool ok2=mn!=mx;
for(int i=0;i<m;i++){
if(a[i]>0&&i+mx>=m)ok1=true;
if(b[i]>0&&i+m-1-mn>=m)ok1=true;
}
if(ok1)printf("%lld\n",ans);
else if(ok2)printf("%lld\n",ans-1);
else printf("0\n");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3904kb
input:
5 2 1 2 3 4 3 1 0 1 0 1 0 4 1 0 0 1 1 1 1 1 5 123456 114514 1919810 233333 234567 20050815 998244353 0 0 0 10 5 3 5 3 2 4 2 4 1 5 9 9 8 2 4 4 3 5 3 0
output:
5 1 2 467900 29
result:
ok 5 number(s): "5 1 2 467900 29"
Test #2:
score: -100
Wrong Answer
time: 62ms
memory: 3904kb
input:
100000 5 0 1 1 1 1 0 0 1 0 0 5 0 0 0 0 0 1 1 1 0 0 5 0 0 2 1 1 0 2 1 0 1 5 0 0 0 0 0 1 2 1 0 0 5 0 1 0 1 1 0 0 1 1 1 5 2 0 0 0 1 1 0 0 0 3 5 2 0 0 1 1 0 2 1 1 1 5 0 0 0 0 2 0 0 0 0 1 5 0 0 0 0 0 0 1 1 0 0 5 4 0 0 0 0 0 0 0 1 0 5 0 0 0 0 1 2 1 1 0 0 5 0 2 3 0 0 0 0 0 1 0 5 1 1 1 0 1 1 0 1 0 1 5 0 0 0...
output:
2 0 4 0 3 3 3 2 0 0 1 1 3 0 3 0 0 0 0 0 0 0 4 0 4 0 0 2 3 3 1 5 0 0 2 0 0 1 1 0 0 3 5 3 2 2 2 0 1 2 0 2 0 3 0 2 1 1 0 1 0 4 1 1 2 2 0 3 3 0 2 0 0 0 0 0 1 2 0 3 4 0 2 5 0 2 1 0 0 0 3 2 3 0 2 0 4 3 3 0 2 2 1 1 3 1 1 0 0 0 1 0 3 2 2 0 2 1 1 0 1 0 0 0 4 1 3 3 2 2 2 0 2 0 0 2 3 1 3 1 0 0 2 3 0 1 2 1 1 1 ...
result:
wrong answer 26th numbers differ - expected: '1', found: '0'