| 23538 | 2026-01-24 12:34:29 | tarjanmici | Walking In The Park | cpp17 | Accepted 100/100 | 377ms | 37932 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <climits>
#include <array>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll n, m, k;
cin >> n >> m >> k;
vector<ll> a(n+1), b(n + 1), pa(n+1), pb(n + 1);
map<ll, ll> ind;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
pa[i] = pa[i - 1] + a[i];
}
for (ll i = 1; i <= m; i++) {
cin >> b[i];
pb[i] = pb[i - 1] + b[i];
ind[pb[i]] = i;
}
vector<ll>lis(n + 1);
for (ll i = 1; i <= n; i++) {
lis[i] = ind[pa[i]];
}
vector<ll> dp(n + 1, LLONG_MAX), bck(n + 1), ki(n+1);
ll mx = 0, kii=0;
for (ll i = 1; i <= n; i++) {
ll x = lower_bound(dp.begin(), dp.end(), lis[i]) - dp.begin();
if (mx < x + 1) {
mx = x + 1;
kii = i;
}
if (lis[i]) {
dp[x] = lis[i];
ki[x] = i;
if(x>0)
bck[i] = ki[x-1];
}
}
vector<int> a1, a2;
if (mx < k||pa[n]!=pb[m]) {
cout << "-1\n";
}
else {
int szml = 0;
for (int i = bck[kii]; szml<k-1; i = bck[i]) {
a1.push_back(i);
a2.push_back(lis[i]);
szml++;
}
reverse(a1.begin(), a1.end());
reverse(a2.begin(), a2.end());
for (int i = 0; i < a1.size(); i++) {
cout << a1[i] << ' ';
}
cout << '\n';
for (int i = 0; i < a2.size(); i++) {
cout << a2[i] << ' ';
}
}
}
| Subtask | Sum | Test | Verdict | Time | Memory | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Accepted | 1ms | 500 KiB | ||||
| 2 | Accepted | 1ms | 316 KiB | ||||
| subtask2 | 19/19 | ||||||
| 3 | Accepted | 214ms | 37932 KiB | ||||
| 4 | Accepted | 202ms | 37676 KiB | ||||
| 5 | Accepted | 203ms | 37168 KiB | ||||
| 6 | Accepted | 211ms | 36656 KiB | ||||
| 7 | Accepted | 214ms | 37172 KiB | ||||
| 8 | Accepted | 201ms | 36656 KiB | ||||
| 9 | Accepted | 216ms | 35952 KiB | ||||
| subtask3 | 23/23 | ||||||
| 10 | Accepted | 2ms | 316 KiB | ||||
| 11 | Accepted | 2ms | 316 KiB | ||||
| 12 | Accepted | 1ms | 500 KiB | ||||
| 13 | Accepted | 1ms | 508 KiB | ||||
| 14 | Accepted | 1ms | 316 KiB | ||||
| 15 | Accepted | 1ms | 316 KiB | ||||
| subtask4 | 16/16 | ||||||
| 16 | Accepted | 2ms | 564 KiB | ||||
| 17 | Accepted | 2ms | 576 KiB | ||||
| 18 | Accepted | 2ms | 456 KiB | ||||
| 19 | Accepted | 2ms | 564 KiB | ||||
| 20 | Accepted | 2ms | 564 KiB | ||||
| 21 | Accepted | 2ms | 564 KiB | ||||
| 22 | Accepted | 2ms | 564 KiB | ||||
| subtask5 | 42/42 | ||||||
| 23 | Accepted | 377ms | 31532 KiB | ||||
| 24 | Accepted | 319ms | 31540 KiB | ||||
| 25 | Accepted | 377ms | 31536 KiB | ||||
| 26 | Accepted | 314ms | 31016 KiB | ||||
| 27 | Accepted | 296ms | 31540 KiB | ||||
| 28 | Accepted | 326ms | 31028 KiB | ||||
| 29 | Accepted | 282ms | 31144 KiB | ||||