235362026-01-24 12:14:18tarjanmiciWalking In The Parkcpp17Wrong answer 81/100372ms37940 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||ki[mx-1]!=n) {
        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] << ' ';
        }
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms508 KiB
subtask20/19
3Accepted209ms37940 KiB
4Accepted199ms37680 KiB
5Accepted210ms37168 KiB
6Accepted196ms36656 KiB
7Accepted200ms37308 KiB
8Wrong answer200ms37172 KiB
9Accepted211ms35760 KiB
subtask323/23
10Accepted1ms336 KiB
11Accepted1ms508 KiB
12Accepted1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
subtask416/16
16Accepted2ms564 KiB
17Accepted2ms564 KiB
18Accepted2ms564 KiB
19Accepted2ms564 KiB
20Accepted2ms460 KiB
21Accepted2ms564 KiB
22Accepted2ms564 KiB
subtask542/42
23Accepted312ms31548 KiB
24Accepted372ms31540 KiB
25Accepted316ms31540 KiB
26Accepted356ms31028 KiB
27Accepted351ms31532 KiB
28Accepted349ms31028 KiB
29Accepted291ms31144 KiB