# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1136046 | bpptidp | Table Tennis (info1cup20_tabletennis) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1.5e5,K=405;
int a[N+K],dp[K][K],n,k;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i=0;i<n+k;++i)
cin>>a[i];
//O(nk+k^4)
unordered_map<int,int>occ;
int f=[](int x){return min(n+k-x-1,404);};
for(int fi=0;fi<=k;++fi){
int se=fi+n-1,x=a[fi]+a[se],c=2;
for(int i=fi+1;i<se;++i)
++occ[a[i]];
for(int i=fi+1;i<se;++i){
if(2*a[i]>x)break;
if(2*a[i]==x){
if(occ[a[i]]<2)continue;
c+=2;
occ[a[i]]-=2;
}else if(occ[x-a[i]]){
c+=2;
--occ[x-a[i]];
--occ[a[i]];
}
}
dp[fi][f(se)]=c;
}
for(int len=n+1;len<=n+k;++len){
for(int fi=0;fi+len<=n+k;++fi){
int se=fi+len-1,x=a[fi]+a[se],mx=0;
for(int i=fi+1;i+n-1<=se+1;++i){
for(int j=se-1;j-n+1>=fi-3;--j){
if(i<=fi||i>=se||j<=fi||j>=se)continue;
if(a[i]+a[j]!=x)continue;
mx=max(mx,dp[i][f(j)]);
}
}
dp[fi][f(se)]=max(dp[fi][f(se)],1+mx);
}
}
//iskreno mrzi me da kucam do kraja sad
//al trebalo bi da daje nekih 87 ovo
cout<<87;
}