제출 #1085616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1085616		vjudge1	Global Warming (CEOI18_glo)	C++17	10 / 100	25 ms	3164 KiB

glo

#include <iostream>
#include <vector>
using namespace std;

int lengthOfLIS(vector<int>& nums)
{

    // Binary search approach
    int n = nums.size();
    vector<int> ans;

    // Initialize the answer vector with the
    // first element of nums
    ans.push_back(nums[0]);

    for (int i = 1; i < n; i++) {
        if (nums[i] > ans.back()) {

            // If the current number is greater
            // than the last element of the answer
            // vector, it means we have found a
            // longer increasing subsequence.
            // Hence, we append the current number
            // to the answer vector.
            ans.push_back(nums[i]);
        }
        else {

            // If the current number is not
            // greater than the last element of
            // the answer vector, we perform
            // a binary search to find the smallest
            // element in the answer vector that
            // is greater than or equal to the
            // current number.

            // The lower_bound function returns
            // an iterator pointing to the first
            // element that is not less than
            // the current number.
            int low = lower_bound(ans.begin(), ans.end(),
                                  nums[i])
                      - ans.begin();

            // We update the element at the
            // found position with the current number.
            // By doing this, we are maintaining
            // a sorted order in the answer vector.
            ans[low] = nums[i];
        }
    }

    // The length of the answer vector
    // represents the length of the
    // longest increasing subsequence.
    return ans.size();
}

// Thanks GFG

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, x;
	cin >> n >> x;
	vector <int> arr(n);
	for (int &i : arr) cin >> i;
	cout << lengthOfLIS(arr);
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25