#include <bits/stdc++.h>
#define int long long
/**
|||||||||| ||||| ||||| ||||||||||
||||||||||||| ||||| ||||| |||||
|||| |||||| ||||| ||||| |||||
||||||||||||||||| ||||||||||||||| ||||||||||
||||||||||||||||||| ||||||||||||||| |||||
||||| ||||| ||||| ||||| |||||
||||| ||||| ||||| ||||| ||||||||||
AHMED;HASSAN;SAEED;
*/
using namespace std;
unordered_map<int,int>mp;
vector<int>v;
vector<pair<int,pair<int,int> > >dp[150000];
int n,k;
int slv(int l,int r){
///cout<<l<<' '<<r<<'\n';
if(dp[l][r-l].first!=-1)
return dp[l][r-l].first;
int ret=0;
for(int i=l+1;i<r&&(i-l)<=k+5;i++){
if(mp[v[r]-(v[i]-v[l])]>i+1){
int ret2=1+slv(i,mp[v[r]-(v[i]-v[l])]-1);
///cout<<'#'<<i<<' '<<mp[v[r]-(v[i]-v[l])]-1<<'\n';
if(ret2>ret){
ret=ret2;
dp[l][r-l].second={i,mp[v[r]-(v[i]-v[l])]-1};
}
}
}
return dp[l][r-l].first=ret;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>k;
n+=k;
v=vector<int>(n);
for(int i=0;i<n;i++){
cin>>v[i];
mp[v[i]]=i+1;
}
for(int i=0;i<=n;i++){
dp[i]=vector<pair<int,pair<int,int> > >(k+5,{-1,{-1,-1}});
}
int ans=0;
int l,r;
///cout<<'h'<<'\n';
for(int i=0;i<=k;i++){
for(int j=n-1;j>=n-k-1&&(i+n-1-j)<=k;j--){
int ret=slv(i,j);
if(ret>ans){
ans=ret;
l=i,r=j;
}
}
}
vector<int>v2(n-k);
int cnt=0;
int tol=0,tor=n-k-1;
while(cnt<n-k){
v2[tol]=v[l],v2[tor]=v[r];
int nl=dp[l][r-l].second.first,nr=dp[l][r-l].second.second;
l=nl,r=nr;
cnt+=2;
tol++; tor--;
}
for(int i=0;i<n-k;i++)
cout<<v2[i]<<' ';
return 0;
}
Compilation message
tabletennis.cpp: In function 'int32_t main()':
tabletennis.cpp:75:23: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
75 | int nl=dp[l][r-l].second.first,nr=dp[l][r-l].second.second;
| ~^~
tabletennis.cpp:75:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
9 ms |
8556 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
28 ms |
18668 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
118 ms |
73700 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
130 ms |
35164 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
8 ms |
7660 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
8 ms |
7916 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
8 ms |
7916 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3100 ms |
262236 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |