Submission #6464565


Source Code Expand

Copy
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

//std::cout << std::fixed << std::setprecision(10)
constexpr long long MOD = 1000000007;

int main()
{
  int N;
  std::cin >> N;
  std::vector<int> A(N);
  for (auto& val: A)
    std::cin >> val;
  auto solve = [&]()
  {
    std::multiset<int> tails;
    tails.insert(A[0]);
    for (int i = 1; i < A.size(); ++i)
    {
      auto val = A[i];
      auto it = tails.lower_bound(val);
      if (it == tails.begin())
      {
        tails.insert(val);
      }
      else
      {
        --it;
        tails.erase(it);
        tails.insert(val);
      }
    }
    return tails.size();
  };
  std::cout << solve() << std::endl;
  return 0;
}

Submission Info

Submission Time
Task E - Sequence Decomposing
User kk09
Language C++14 (GCC 5.4.1)
Score 500
Code Size 974 Byte
Status AC
Exec Time 78 ms
Memory 5376 KB

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 76 ms 5376 KB
killer_01 AC 77 ms 5248 KB
killer_02 AC 73 ms 4992 KB
killer_03 AC 78 ms 5248 KB
killer_04 AC 68 ms 3712 KB
killer_05 AC 69 ms 3840 KB
many_dup_01 AC 54 ms 640 KB
many_dup_02 AC 58 ms 640 KB
many_dup_03 AC 54 ms 640 KB
many_dup_04 AC 56 ms 768 KB
many_dup_05 AC 56 ms 896 KB
many_dup_06 AC 52 ms 768 KB
many_dup_07 AC 54 ms 1536 KB
many_dup_08 AC 53 ms 1792 KB
many_dup_09 AC 50 ms 1664 KB
many_dup_10 AC 54 ms 2944 KB
many_dup_11 AC 54 ms 2176 KB
many_dup_12 AC 50 ms 2048 KB
rand_max_01 AC 54 ms 640 KB
rand_max_02 AC 53 ms 640 KB
rand_max_03 AC 52 ms 640 KB
rand_max_04 AC 53 ms 640 KB
rand_max_05 AC 51 ms 640 KB
rand_max_06 AC 52 ms 640 KB
rand_max_07 AC 53 ms 640 KB
rand_max_08 AC 56 ms 640 KB
rand_max_09 AC 51 ms 640 KB
rand_max_10 AC 56 ms 640 KB
rand_max_11 AC 52 ms 640 KB
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sorted_ascending AC 32 ms 640 KB
sorted_descending AC 63 ms 5120 KB
unique_perm_01 AC 42 ms 640 KB
unique_perm_02 AC 43 ms 640 KB