Submission #897555

#	Time	Username	Problem	Language	Result	Execution time	Memory
897555		AI_2512	Money (IZhO17_money)	C++17	0 / 100	0 ms	348 KiB

money

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int min_subsegments_to_sort(int N, vector<int>& banknotes) {
    vector<int> increasing_subsequences(N, 1);

    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (banknotes[i] >= banknotes[j]) {
                increasing_subsequences[i] = max(increasing_subsequences[i], increasing_subsequences[j] + 1);
            }
        }
    }

    return N - *max_element(increasing_subsequences.begin(), increasing_subsequences.end());
}

int main() {
    // Input
    int N;
    cin >> N;

    vector<int> banknotes(N);
    for (int i = 0; i < N; ++i) {
        cin >> banknotes[i];
    }

    // Output
    int result = min_subsegments_to_sort(N, banknotes);
    cout << result << endl;

    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55