9682 2024. 02. 25 11:41:51 zeytonx Hadjárat cpp17 Időlimit túllépés 0/100 298ms 15136 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef set<ll> sll;
typedef queue<ll> qll;
typedef priority_queue<ll> pqll;
typedef vector<vll> v2ll;
typedef map<ll,ll> mll;
typedef vector<pll> vpll;
typedef map<pll,ll> mpll;
typedef vector<vpll> v2pll;
typedef vector<sll> v2sll;
#define fs first
#define sc second
#define pb push_back

const ll MOD = 1e9+7;

void solve()
{
    ll n;
    cin >> n;
    vll R(n), A(n);
    for(ll i = 0; i < n; i++)
        cin >> R[i] >> A[i];
    vll dp(n, 1);
    vll parent(n);
    for(ll i = 0; i < n; i++)
        parent[i] = i;
    ll last = 0, last_v = 0;
    for(ll i = 0; i < n; i++)
    {
        for(ll j = i; j >= 0; j--)
            if(R[j] < R[i] && A[j] < A[i])
            {
                if(dp[j]+1 > dp[i])
                {
                    dp[i] = dp[j]+1;
                    parent[i] = j;
                }
            }
        if(i != 0 && dp[i-1] > dp[i])
        {
            dp[i] = dp[i-1];
            parent[i] = parent[i-1];
        }
        if(last_v < dp[i])
        {
            last = i;
            last_v = dp[i];
        }
    }

    cout << dp[n-1] << "\n";
    ll index = parent[n-1];
    vll ans;
    ans.pb(last);
    while(parent[index] != index)
    {
        ans.pb(index);
        index = parent[index];
    }
    ans.pb(index);
    reverse(ans.begin(), ans.end());
    for(ll i : ans)
        cout << i+1 << " ";
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--)
        solve();
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 0/100
1 Elfogadva 0/0 3ms 2080 KiB
2 Időlimit túllépés 0/0 298ms 3652 KiB
3 Hibás válasz 0/4 3ms 2976 KiB
4 Hibás válasz 0/4 3ms 3180 KiB
5 Hibás válasz 0/4 3ms 3392 KiB
6 Hibás válasz 0/4 3ms 3604 KiB
7 Hibás válasz 0/4 3ms 3692 KiB
8 Hibás válasz 0/4 3ms 3704 KiB
9 Hibás válasz 0/4 3ms 3844 KiB
10 Hibás válasz 0/4 6ms 3972 KiB
11 Hibás válasz 0/4 79ms 4408 KiB
12 Időlimit túllépés 0/4 264ms 3616 KiB
13 Időlimit túllépés 0/6 266ms 3820 KiB
14 Időlimit túllépés 0/6 241ms 4556 KiB
15 Időlimit túllépés 0/6 264ms 5068 KiB
16 Időlimit túllépés 0/6 264ms 6324 KiB
17 Időlimit túllépés 0/6 261ms 7600 KiB
18 Időlimit túllépés 0/6 264ms 8756 KiB
19 Időlimit túllépés 0/6 273ms 10240 KiB
20 Időlimit túllépés 0/6 252ms 12248 KiB
21 Időlimit túllépés 0/6 250ms 13808 KiB
22 Időlimit túllépés 0/6 266ms 15136 KiB