#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 |