103622024-04-01 11:08:00MagyarKendeSZLGHadjáratcpp17Time limit exceeded 36/100300ms5232 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);

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            if (R[j] < R[i] && A[j] < A[i]) {
                if (dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
        }
    }

    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";
}
SubtaskSumTestVerdictTimeMemory
base36/100
1Accepted0/03ms1824 KiB
2Time limit exceeded0/0300ms2224 KiB
3Accepted4/43ms2384 KiB
4Accepted4/42ms2364 KiB
5Accepted4/43ms2588 KiB
6Accepted4/42ms2584 KiB
7Accepted4/43ms2784 KiB
8Accepted4/43ms3012 KiB
9Accepted4/43ms3124 KiB
10Accepted4/46ms3116 KiB
11Accepted4/481ms3432 KiB
12Time limit exceeded0/4259ms3696 KiB
13Time limit exceeded0/6243ms3104 KiB
14Time limit exceeded0/6270ms3600 KiB
15Time limit exceeded0/6270ms4048 KiB
16Time limit exceeded0/6270ms4212 KiB
17Time limit exceeded0/6270ms4792 KiB
18Time limit exceeded0/6273ms4724 KiB
19Time limit exceeded0/6261ms4900 KiB
20Time limit exceeded0/6268ms5040 KiB
21Time limit exceeded0/6273ms5224 KiB
22Time limit exceeded0/6254ms5232 KiB