QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#137738#6794. Sequence to Sequencevme50WA 109ms4808kbC++171.4kb2023-08-10 17:12:312023-08-12 03:46:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-12 03:46:54]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:WA
  • 用时:109ms
  • 内存:4808kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 17:12:51]
  • 评测
  • 测评结果:0
  • 用时:121ms
  • 内存:4812kb
  • [2023-08-10 17:12:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define ll long long
const int INF=1e9;
int T,n,o,w1,w2,a[N],b[N],lim[N];ll ans;
void slv()
{
	scanf("%d",&n);o=w1=w2=ans=a[n+1]=b[n+1]=0;
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=n;++i) scanf("%d",&b[i]);
	for(int i=1;i<=n;++i) if(!a[i] && b[i]) {printf("-1\n");return;}
	while(1)
	{
		int t=0;for(int i=o+1;i<=n;++i) if((b[i] && w1>=a[i]) || w1<a[i]-b[i]) {t=i;break;}
		if(t)
		{
			if(b[t] && w1>=a[t])
			{
				lim[t]=a[t]-1;for(int i=t-1;i>o;--i) lim[i]=max(lim[i+1],a[i]-b[i]);
				for(int i=o+1,w;i<t;++i) if(b[i])
				{
					w=w1-w2-a[i]+b[i];ans+=abs(w);
					w=max(min(w,w1-lim[i]),0);w1-=w;w2=w1-a[i]+b[i];
				}ans+=abs(w1-a[t]+1)+abs(w2-b[t]+1);w1=a[t]-1;w2=b[t]-1;o=t;
			}
			else
			{
				lim[t]=a[t]-b[t];for(int i=t-1;i>o;--i) lim[i]=min(lim[i+1],b[i]?a[i]-1:INF);
				for(int i=o+1,w;i<t;++i) if(b[i])
				{
					w=w2-w1+a[i]-b[i];ans+=abs(w);
					w=max(min(w,lim[i]-w1),0);w1+=w;w2=w1-a[i]+b[i];
				}ans+=abs(w1-a[t]+b[t]);w1=a[t]-b[t];if(b[t]) ans+=w2,w2=0;o=t;
			}
		}
		else
		{
			lim[n+1]=0;for(int i=n;i>o;--i) lim[i]=max(lim[i+1],a[i]-b[i]);
			for(int i=o+1,w;i<=n;++i) if(b[i])
			{
				w=w1-w2-a[i]+b[i];ans+=abs(w);
				w=max(min(w,w1-lim[i]),0);w1-=w;w2=w1-a[i]+b[i];
			}ans+=w1+w2;break;
		}
	}printf("%lld\n",ans/2);
}
int main() {scanf("%d",&T);while(T--) slv();return 0;}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3676kb

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: -100
Wrong Answer
time: 109ms
memory: 4808kb

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:

wrong answer 376th words differ - expected: '3', found: '4'