QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353165 | #8057. Best Carry Player 4 | ucup-team134# | WA | 69ms | 3908kb | C++17 | 1.2kb | 2024-03-13 22:06:12 | 2024-03-13 22:06:12 |
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;
int 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;
}
}
if(large)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: 1ms
memory: 3840kb
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: 69ms
memory: 3908kb
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 -1 4 -1 4 3 3 2 -1 -1 1 1 3 0 3 0 0 -1 -1 0 0 0 4 0 4 1 -1 2 4 3 1 5 0 -1 2 0 0 1 1 -1 0 3 5 3 2 2 2 -1 1 2 2 2 -1 4 0 2 1 1 0 1 -1 4 0 0 2 2 -1 3 3 -1 2 -1 1 -1 0 1 1 2 0 3 4 -1 2 5 -1 2 1 0 0 -1 3 2 3 -1 2 0 4 3 3 0 2 2 0 1 3 1 1 -1 0 -1 1 -1 3 2 2 -1 2 1 1 0 1 -1 0 2 4 1 3 3 2 2 2 -1 2 -1 0 2 3...
result:
wrong answer 2nd numbers differ - expected: '0', found: '-1'