QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246417 | #6794. Sequence to Sequence | XZC0920 | AC ✓ | 19ms | 9764kb | C++14 | 2.4kb | 2023-11-10 20:06:42 | 2023-11-10 20:06:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const ll I=1e18;
int t,n,a[N],b[N];
ll ans,x,y,z;
namespace IO
{
const int S=(1<<20);
char in[S],out[S],*p1=in,*p2=in,*p3=out;
char gc() {return p1==p2&&(p2=(p1=in)+fread(in,1,S,stdin),p1==p2)?EOF:*p1++;}
void flush() {fwrite(out,1,p3-out,stdout);p3=out;}
void pc(char c)
{
if(p3==out+S) flush();
*p3++=c;
}
template<class T>void read(T &x)
{
x=0;int t=0;char c=gc();
for(;!isdigit(c);c=gc()) if(c=='-') t=1;
for(;isdigit(c);c=gc()) x=(x<<1)+(x<<3)+(c^48);
if(t) x=-x;
}
template<class T>void write(T x,char c='\n')
{
if(x<0) pc('-'),x=-x;
static int s[40],top=0;
do s[++top]=x%10,x/=10;while(x);
while(top) pc(s[top--]+48);
pc(c);
}
struct F {~F(){flush();};}f;
}
using IO::read;
using IO::write;
void solve()
{
read(n);ans=0;x=y=z=0;
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++) read(b[i]);
for(int i=1;i<=n;i++)
{
if(b[i]==0)
{
if(x<a[i])
{
ll v=min(z,a[i]-x);
x+=v,y+=v,z-=v;ans+=v;
if(x<a[i]) ans+=(a[i]-x),x=a[i];
}
}
else
{
if(a[i]==0) return write(-1),void();
if(a[i]-b[i]<=x&&b[i]-a[i]>y)
{
ll v=min(z,b[i]-a[i]-y);
ans+=v,x+=v,y+=v,z-=v;
}
if(b[i]-a[i]<=y&&a[i]-b[i]>x)
{
ll v=min(z,a[i]-b[i]-x);
ans+=v,x+=v,y+=v,z-=v;
}
x=min(x,(ll)a[i]-1);y=min(y,(ll)b[i]-1);
if(a[i]-b[i]<=x&&b[i]-a[i]<=y)
{
if(x+b[i]-y-a[i]>=0) z=min({z,a[i]-1-x,b[i]-1-y})+(x+b[i]-y-a[i]),x=y+a[i]-b[i];
else z=min({z,a[i]-1-x,b[i]-1-y})+(y+a[i]-x-b[i]),y=x+b[i]-a[i];
continue;
}
if(a[i]-b[i]<=x)
{
ans+=(b[i]-a[i]-y);
z=x;x=0;y=b[i]-a[i];
continue;
}
if(b[i]-a[i]<=y)
{
ans+=(a[i]-b[i]-x);
z=y;y=0;x=a[i]-b[i];
continue;
}
}
}
write(ans);
}
int main()
{
read(t);
while(t--) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7540kb
input:
2 5 1 1 1 1 1 2 0 2 0 2 7 3 1 2 3 2 1 4 2 0 0 0 0 0 2
output:
3 3
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 19ms
memory: 9764kb
input:
110121 5 0 0 0 0 0 1 4 5 4 1 5 1 0 0 0 0 0 6 8 6 1 5 2 0 0 0 0 4 4 1 3 6 5 3 0 0 0 0 5 1 1 7 6 5 4 0 0 0 0 6 8 7 0 8 5 5 0 0 0 0 5 9 7 7 5 5 6 0 0 0 0 9 2 2 8 0 5 7 0 0 0 0 9 4 7 0 9 5 8 0 0 0 0 6 7 3 7 5 5 9 0 0 0 0 4 0 9 1 4 5 0 1 0 0 0 0 6 6 3 0 5 1 1 0 0 0 3 4 3 4 9 5 2 1 0 0 0 0 4 0 1 4 5 3 1 0...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 110121 tokens
Extra Test:
score: 0
Extra Test Passed