10363 | 2024. 04. 01 11:36:23 | MagyarKendeSZLG | Hadjárat | cpp17 | Időlimit túllépés 36/100 | 300ms | 5968 KiB |
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define size(v) (int)v.size()
using namespace std;
using ll = long long;
int main() {
cin.tie(0), ios::sync_with_stdio(0);
int N;
cin >> N;
vector<int> R(N + 1), A(N + 1);
for (int i = 1; i <= N; i++) {
cin >> R[i] >> A[i];
}
vector<int> dp(N + 1, 1), prev(N + 1, -1);
set<array<int, 2>> s;
s.insert({1, 1});
for (int i = 2; i <= N; i++) {
for (auto it = s.end() ;; it--) {
if (it == s.end()) it--;
auto [x, j] = *it;
if (R[j] < R[i] && A[j] < A[i]) {
dp[i] = x + 1;
prev[i] = j;
break;
}
if (it == s.begin()) break;
}
s.insert({dp[i], i});
}
int mxi = max_element(all(dp)) - dp.begin();
cout << dp[mxi] << "\n";
stack<int> path;
while (mxi != -1) {
path.push(mxi);
mxi = prev[mxi];
}
while (!path.empty()) {
cout << path.top() << " ";
path.pop();
}
cout << "\n";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 36/100 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Időlimit túllépés | 0/0 | 300ms | 2732 KiB | |||
3 | Elfogadva | 4/4 | 3ms | 2392 KiB | |||
4 | Elfogadva | 4/4 | 3ms | 2464 KiB | |||
5 | Elfogadva | 4/4 | 3ms | 2516 KiB | |||
6 | Elfogadva | 4/4 | 3ms | 2748 KiB | |||
7 | Elfogadva | 4/4 | 2ms | 2736 KiB | |||
8 | Elfogadva | 4/4 | 3ms | 2876 KiB | |||
9 | Elfogadva | 4/4 | 3ms | 3092 KiB | |||
10 | Elfogadva | 4/4 | 4ms | 3236 KiB | |||
11 | Elfogadva | 4/4 | 61ms | 3732 KiB | |||
12 | Időlimit túllépés | 0/4 | 244ms | 4564 KiB | |||
13 | Időlimit túllépés | 0/6 | 237ms | 4792 KiB | |||
14 | Időlimit túllépés | 0/6 | 241ms | 3772 KiB | |||
15 | Időlimit túllépés | 0/6 | 270ms | 3904 KiB | |||
16 | Időlimit túllépés | 0/6 | 261ms | 4500 KiB | |||
17 | Időlimit túllépés | 0/6 | 254ms | 4964 KiB | |||
18 | Időlimit túllépés | 0/6 | 270ms | 5152 KiB | |||
19 | Időlimit túllépés | 0/6 | 223ms | 5348 KiB | |||
20 | Időlimit túllépés | 0/6 | 238ms | 5804 KiB | |||
21 | Időlimit túllépés | 0/6 | 270ms | 5876 KiB | |||
22 | Időlimit túllépés | 0/6 | 266ms | 5968 KiB |