QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#798284 | #1281. Longest Common Subsequence | SFlyer | TL | 7ms | 45456kb | C++14 | 1.9kb | 2024-12-04 11:08:22 | 2024-12-04 11:08:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6+6;
int n,m,a[N],b[N],sa[N],sb[N],la[N],ra[N],lb[N],rb[N];
struct fenwick {
int t[N*4];
int B=N*2;
void init(){
for (int i=0; i<N*4; i++) t[i]=-1e9;
}
void M(int p,int v){
p+=B;
while (p<N*4){
t[p]=max(t[p],v),p+=p&-p;
}
}
int Q(int p){
int ans=-1e9;
p+=B;
while (p){
ans=max(ans,t[p]),p-=p&-p;
}
return ans;
}
} t[2];
void solve(){
cin>>n>>m;
for (int i=1; i<=n; i++){
cin>>a[i];
sa[i]=sa[i-1]+(a[i]==2);
la[i]=n+1,ra[i]=0;
}
for (int i=1; i<=m; i++){
cin>>b[i];
sb[i]=sb[i-1]+(b[i]==2);
lb[i]=m+1,rb[i]=0;
}
int c=0;
for (int i=1; i<=n; i++){
if (a[i]==1) la[++c]=i;
}
c=0;
for (int i=1; i<=m; i++){
if (b[i]==1) lb[++c]=i;
}
ra[0]=n+1,c=0;
for (int i=n; i; i--){
if (a[i]==3) ra[++c]=i;
}
rb[0]=m+1,c=0;
for (int i=m; i; i--){
if (b[i]==3) rb[++c]=i;
}
t[0].init(),t[1].init();
int ans=0;
for (int j=min(n,m),i=0; j>=0; j--){
while (i<=min(n,m) && la[i]<ra[j] && lb[i]<rb[j]){
t[0].M(sa[la[i]]-sb[lb[i]],-sb[lb[i]]+i);
t[1].M(sb[lb[i]]-sa[la[i]],-sa[la[i]]+i);
i++;
}
ans=max(ans,t[0].Q(sa[ra[j]-1]-sb[rb[j]-1])+sb[rb[j]-1]+j);
ans=max(ans,t[1].Q(sb[rb[j]-1]-sa[ra[j]-1])+sa[ra[j]-1]+j);
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while (t--){
solve();
}
return 0;
}
// TRY! TRY! TRY!
/*
Think twice before coding. Have you overkilled?
Think twice before submitting.
Check on the samples and constraints carefully.
*/
/*
Be brave to guess.
Is your former/first approach correct?
Follow your intuition.
Use a notebook to note down your ideas and check whether they are correct.
*/
/*
A simple brute force may work? There is some limit on the answer?
Try to find patterns.
*/
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 45456kb
input:
3 3 3 1 2 3 1 2 3 3 3 1 1 1 1 1 2 3 3 1 3 2 1 2 3
output:
3 2 2
result:
ok 3 tokens
Test #2:
score: -100
Time Limit Exceeded
input:
139889 1 10 2 2 1 2 2 3 1 1 2 3 3 7 1 3 2 3 3 1 1 2 2 6 1 2 1 3 1 1 1 1 8 7 3 1 3 3 2 2 3 1 3 2 2 1 3 3 3 10 3 3 2 1 1 2 2 1 1 1 1 3 1 1 5 2 1 2 1 3 1 1 2 1 4 1 3 3 3 3 7 2 3 1 2 1 2 2 3 3 2 6 2 3 1 1 2 1 3 1 3 1 4 1 3 1 1 3 4 2 2 3 2 3 1 3 1 8 1 1 1 3 1 3 3 3 1 4 1 1 3 3 3 1 10 10 3 1 2 1 2 2 2 2 1...