96822024-02-25 11:41:51zeytonxHadjáratcpp17Időlimit túllépés 0/100298ms15136 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ÖsszpontTesztVerdiktIdőMemória
base0/100
1Elfogadva0/03ms2080 KiB
2Időlimit túllépés0/0298ms3652 KiB
3Hibás válasz0/43ms2976 KiB
4Hibás válasz0/43ms3180 KiB
5Hibás válasz0/43ms3392 KiB
6Hibás válasz0/43ms3604 KiB
7Hibás válasz0/43ms3692 KiB
8Hibás válasz0/43ms3704 KiB
9Hibás válasz0/43ms3844 KiB
10Hibás válasz0/46ms3972 KiB
11Hibás válasz0/479ms4408 KiB
12Időlimit túllépés0/4264ms3616 KiB
13Időlimit túllépés0/6266ms3820 KiB
14Időlimit túllépés0/6241ms4556 KiB
15Időlimit túllépés0/6264ms5068 KiB
16Időlimit túllépés0/6264ms6324 KiB
17Időlimit túllépés0/6261ms7600 KiB
18Időlimit túllépés0/6264ms8756 KiB
19Időlimit túllépés0/6273ms10240 KiB
20Időlimit túllépés0/6252ms12248 KiB
21Időlimit túllépés0/6250ms13808 KiB
22Időlimit túllépés0/6266ms15136 KiB