QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#290703 | #6794. Sequence to Sequence | Crysfly# | AC ✓ | 29ms | 6496kb | C++14 | 2.0kb | 2023-12-25 09:39:09 | 2023-12-25 09:39:10 |
Judging History
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