oj.uz

Submission #897555

# Submission time Handle Problem Language Result Execution time Memory
897555 2024-01-03T11:59:35 Z AI_2512 Money (IZhO17_money) C++17
0 / 100
 0 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -