Submission #1206028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206028		alwaus424	LIS (INOI20_lis)	C++20	20 / 100	4094 ms	488 KiB

Main

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

int findLIS(const vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n, 1);
    int lis = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        lis = max(lis, dp[i]);
    }
    return lis;
}

int main() {
    int q;
    cin >> q;
    vector<int> bags;
    for (int i = 0; i < q; ++i) {
        int pi, xi;
        cin >> pi >> xi;
        bags.insert(bags.begin() + pi - 1, xi);
        cout << findLIS(bags) << endl;
    }
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80