QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#290703#6794. Sequence to SequenceCrysfly#AC ✓29ms6496kbC++142.0kb2023-12-25 09:39:092023-12-25 09:39:10

Judging History

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

  • [2023-12-25 09:39:10]
  • 评测
  • 测评结果:AC
  • 用时:29ms
  • 内存:6496kb
  • [2023-12-25 09:39:09]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
 
#define maxn 1000005
#define inf 0x3f3f3f3f

int n,s[maxn],t[maxn];

/*
for t[i]==0 : sum1>=s[i]
for t[i]>0  : sum1<=s[i]-1 , -sum1+sum2==d[i].
minimize : \sum cnt[i]

after dual:

for t[i]==0 : a[i] in {0,1}
for t[i]>0  : a[i] in {0,-1} , b[i] in {-1,0,1}

for all lines:
\sum a[i]-\sum b[i]<=1
\sum b[i]<=1

maximize : 
for t[i]==0 : a[i]*s[i]
for t[i]>0  : a[i]*(s[i]-1) + b[i]*d[i]
*/

int f[4],g[4],w[2];

void work()
{
	n=read();
	For(i,1,n)s[i]=read();
	For(i,1,n)t[i]=read();
	For(i,1,n)if(s[i]==0&&t[i])return puts("-1"),void();
	memset(f,-63,sizeof f),f[0]=0;
	For(i,1,n){
		memset(g,-63,sizeof g);
		For(b,-1,1){
			if(t[i]==0 && b)continue;
			For(a,b-1,b+1){
				if(t[i]==0 && a<0) continue;
				if(t[i]>0 && a>0) continue;
				int now=(t[i]-s[i])*b;
				if(t[i]==0) now+=s[i]*a;
				else now+=(s[i]-1)*a;
				w[0]=a-b;
				w[1]=b;
				For(s,0,3){
					bool ok=1;
					int t=0;
					For(j,0,1){
						int tmp=((s>>j&1)+w[j]);
						if(tmp>1) {
							ok=0;
							break;
						}
						else if(tmp==1) t|=(1<<j);
					}
					if(ok) g[t]=max(g[t],f[s]+now);
				}
			}
		}
		swap(f,g);
	}
	cout<<*max_element(f,f+4)<<"\n";
}

signed main()
{
	int T=read();
	while(T--)work();
	return 0;
}
/*

*/

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5596kb

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: 29ms
memory: 6496kb

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