#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
const int mxN = 150001;
const int mxK = 401;
int N, K;
int A[mxN];
map<int,int> dpL[mxN], dpR[mxN];
map<int,int> paL[mxN], paR[mxN];
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> K;
N += K;
FOR(i,1,N){
cin >> A[i];
}
if (N-K == 2) {
cout << A[1] _ A[2] << '\n';
return 0;
}
FOR(i,2,N){
FOR(j,max(1,i-K-1),i-1){
int diff = A[i]-A[j];
int r = dpL[j].count(diff) ? dpL[j][diff]+1 : 2;
if (!dpL[i].count(diff) || dpL[i][diff] < r) {
dpL[i][diff] = r;
paL[i][diff] = j;
}
}
}
RFOR(i,N-1,1){
FOR(j,i+1,min(N,i+K+1)){
int diff = A[j]-A[i];
int r = dpR[j].count(diff) ? dpR[j][diff]+1 : 2;
if (!dpR[i].count(diff) || dpR[i][diff] < r) {
dpR[i][diff] = r;
paR[i][diff] = j;
}
}
}
map<int,int> slide;
FOR(i,1,N){
for (auto& x : dpR[i]) {
if (slide.count(x.first) && min(dpL[slide[x.first]][x.first], x.second)*2 >= N-K) {
//cout << "YES" _ x.first _ slide[x.first] _ i << endl;
int a = slide[x.first], b = i;
vector<int> ans;
while (SZ(ans) < (N-K)/2) ans.push_back(a), a = paL[a][x.first];
reverse(ALL(ans));
while (SZ(ans) < N-K) ans.push_back(b), b = paR[b][x.first];
for (int& x : ans) {
cout << A[x] << ' ';
}
cout << endl;
return 0;
}
}
for (auto& x : dpL[i]) {
if (!slide.count(x.first) || dpL[slide[x.first]][x.first] < x.second) {
slide[x.first] = i;
}
}
}
assert(false);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
51 ms |
59104 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
36392 KB |
Output is correct |
2 |
Execution timed out |
3087 ms |
432260 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3058 ms |
28996 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
30100 KB |
Output is correct |
2 |
Correct |
34 ms |
31508 KB |
Output is correct |
3 |
Correct |
29 ms |
31276 KB |
Output is correct |
4 |
Correct |
29 ms |
31436 KB |
Output is correct |
5 |
Correct |
28 ms |
31280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
28492 KB |
Output is correct |
2 |
Correct |
17 ms |
28492 KB |
Output is correct |
3 |
Correct |
20 ms |
28464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
47 ms |
57804 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
48 ms |
57716 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
45648 KB |
Output is correct |
2 |
Runtime error |
65 ms |
58748 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |