Submission #6459386

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
using namespace std;

int solve(int n, const vector<int> & a) {
    multiset<int> fronts;  // of LISs
    REP_R (i, n) {
        auto it = fronts.upper_bound(a[i]);
        if (it != fronts.end()) {
            fronts.erase(it);
        }
        fronts.insert(a[i]);
    }
    return fronts.size();
}

int main() {
    int n; cin >> n;
    vector<int> a(n);
    REP (i, n) {
        cin >> a[i];
    }
    cout << solve(n, a) << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Sequence Decomposing
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 500
Code Size 600 Byte
Status AC
Exec Time 80 ms
Memory 5376 KiB

Judge Result

Set Name All Sample
Score / Max Score 500 / 500 0 / 0
Status
AC × 35
AC × 2
Set Name Test Cases
All all_same, killer_01, killer_02, killer_03, killer_04, killer_05, many_dup_01, many_dup_02, many_dup_03, many_dup_04, many_dup_05, many_dup_06, many_dup_07, many_dup_08, many_dup_09, many_dup_10, many_dup_11, many_dup_12, rand_max_01, rand_max_02, rand_max_03, rand_max_04, rand_max_05, rand_max_06, rand_max_07, rand_max_08, rand_max_09, rand_max_10, rand_max_11, sample_01, sample_02, sorted_ascending, sorted_descending, unique_perm_01, unique_perm_02
Sample sample_01, sample_02
Case Name Status Exec Time Memory
all_same AC 80 ms 5376 KiB
killer_01 AC 76 ms 5248 KiB
killer_02 AC 70 ms 4992 KiB
killer_03 AC 76 ms 5248 KiB
killer_04 AC 66 ms 3712 KiB
killer_05 AC 67 ms 3840 KiB
many_dup_01 AC 54 ms 640 KiB
many_dup_02 AC 54 ms 640 KiB
many_dup_03 AC 53 ms 640 KiB
many_dup_04 AC 56 ms 768 KiB
many_dup_05 AC 56 ms 896 KiB
many_dup_06 AC 51 ms 768 KiB
many_dup_07 AC 59 ms 1536 KiB
many_dup_08 AC 63 ms 1792 KiB
many_dup_09 AC 55 ms 1664 KiB
many_dup_10 AC 63 ms 2944 KiB
many_dup_11 AC 64 ms 2176 KiB
many_dup_12 AC 56 ms 2048 KiB
rand_max_01 AC 53 ms 640 KiB
rand_max_02 AC 52 ms 640 KiB
rand_max_03 AC 50 ms 640 KiB
rand_max_04 AC 52 ms 640 KiB
rand_max_05 AC 50 ms 640 KiB
rand_max_06 AC 51 ms 640 KiB
rand_max_07 AC 52 ms 640 KiB
rand_max_08 AC 53 ms 640 KiB
rand_max_09 AC 50 ms 640 KiB
rand_max_10 AC 54 ms 640 KiB
rand_max_11 AC 51 ms 640 KiB
sample_01 AC 1 ms 256 KiB
sample_02 AC 1 ms 256 KiB
sorted_ascending AC 32 ms 640 KiB
sorted_descending AC 63 ms 5120 KiB
unique_perm_01 AC 41 ms 640 KiB
unique_perm_02 AC 42 ms 640 KiB