235362026-01-24 12:14:18tarjanmiciWalking In The Parkcpp17Hibás válasz 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] << ' ';
        }
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms508 KiB
subtask20/19
3Elfogadva209ms37940 KiB
4Elfogadva199ms37680 KiB
5Elfogadva210ms37168 KiB
6Elfogadva196ms36656 KiB
7Elfogadva200ms37308 KiB
8Hibás válasz200ms37172 KiB
9Elfogadva211ms35760 KiB
subtask323/23
10Elfogadva1ms336 KiB
11Elfogadva1ms508 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
subtask416/16
16Elfogadva2ms564 KiB
17Elfogadva2ms564 KiB
18Elfogadva2ms564 KiB
19Elfogadva2ms564 KiB
20Elfogadva2ms460 KiB
21Elfogadva2ms564 KiB
22Elfogadva2ms564 KiB
subtask542/42
23Elfogadva312ms31548 KiB
24Elfogadva372ms31540 KiB
25Elfogadva316ms31540 KiB
26Elfogadva356ms31028 KiB
27Elfogadva351ms31532 KiB
28Elfogadva349ms31028 KiB
29Elfogadva291ms31144 KiB