oj.uz

Submission #858344

# Submission time Handle Problem Language Result Execution time Memory
858344 2023-10-08T08:11:51 Z ily2003 Studentsko (COCI14_studentsko) C++14
100 / 100
 2 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n,k,dp[5001];
pair<int,int> a[5001];
vector<int> vec;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i=0;i<n;i++) {
        cin >> a[i].f;
        a[i].s=i;
    }
    sort(a,a+n);
    for(int i=0;i<n;i++) dp[a[i].s]=i/k;
    for(int i=0;i<n;i++) {
        if(vec.empty() || dp[i]>=vec.back()) vec.push_back(dp[i]);
        else {
            int so=upper_bound(vec.begin(),vec.end(),dp[i])-vec.begin();
            vec[so]=dp[i];
        }
    }
    cout<<n-vec.size()<<'\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct