#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];
int res[2005][2005], pa[2005][2005];
int dp(int l, int r) {
if (l+1 == r) return 0;
if (~res[l][r]) return res[l][r];
res[l][r] = r-l-2;
int a = l+1, b = r-1, c = 0;
while (a < b && c <= K) {
int cur = A[a]+A[b], tgt = A[l]+A[r];
if (cur == tgt) {
res[l][r] = dp(a,b)+c;
break;
}
if (cur < tgt) ++a;
else --b;
++c;
}
return res[l][r];
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> K;
FOR(i,1,N+K){
cin >> A[i];
}
memset(res,-1,sizeof res);
memset(pa,-1,sizeof pa);
FOR(i,1,K+1){
RFOR(j,N+K,N+i-1){
//TRACE(i _ j _ dp(i,j) _ i-1 _ N+K-j);
if (j-i+1-dp(i,j) >= N && dp(i,j) + (i-1) + (N+K-j) <= K) {
//TRACE(i _ j);
int l = i, r = j;
int a = i+1, b = j-1;
vector<int> ls = {l}, rs = {r};
while (SZ(ls)+SZ(rs) < N) {
int cur = A[a]+A[b], tgt = A[l]+A[r];
if (cur == tgt) {
l = a, r = b;
ls.push_back(a);
rs.push_back(b);
}
if (cur < tgt) ++a;
else --b;
}
for (int& x : ls) cout << A[x] << ' ';
reverse(ALL(rs));
for (int& x : rs) cout << A[x] << ' ';
return 0;
}
}
}
assert(false);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
31820 KB |
Output is correct |
2 |
Correct |
14 ms |
31760 KB |
Output is correct |
3 |
Correct |
16 ms |
31856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
48 ms |
64564 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3082 ms |
836 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
31700 KB |
Output is correct |
2 |
Correct |
16 ms |
31760 KB |
Output is correct |
3 |
Correct |
17 ms |
31732 KB |
Output is correct |
4 |
Correct |
19 ms |
31692 KB |
Output is correct |
5 |
Correct |
19 ms |
31676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
31716 KB |
Output is correct |
2 |
Correct |
17 ms |
31692 KB |
Output is correct |
3 |
Correct |
15 ms |
31728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
31684 KB |
Output is correct |
2 |
Correct |
15 ms |
31844 KB |
Output is correct |
3 |
Correct |
17 ms |
31820 KB |
Output is correct |
4 |
Correct |
15 ms |
31852 KB |
Output is correct |
5 |
Correct |
15 ms |
31788 KB |
Output is correct |
6 |
Correct |
17 ms |
31820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
31768 KB |
Output is correct |
2 |
Execution timed out |
3080 ms |
844 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
31736 KB |
Output is correct |
2 |
Runtime error |
25 ms |
1528 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |