oj.uz

Submission #17499

# Submission time Handle Problem Language Result Execution time Memory
17499 2015-12-22T02:36:22 Z kdh9949 Studentsko (COCI14_studentsko) C++
100 / 100
 55 ms 1140 KB 
#include <cstdio>
#include <algorithm>
using namespace std;

int n, k, a[5010], b[5010], dt[5010], ans;

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++){
        scanf("%d", a + i);
        b[i] = a[i];
    }
    sort(b, b + n);
    for(int i = 0; i < n; i++){
        a[i] = (lower_bound(b, b + n, a[i]) - b) / k;
    }
    dt[0] = 1;
    for(int i = 1; i < n; i++){
        dt[i] = 1;
        for(int j = 0; j < i; j++){
            if(a[j] <= a[i]) dt[i] = max(dt[i], dt[j] + 1);
        }
    }
    for(int i = 1; i < n; i++) ans = max(ans, dt[i]);
    printf("%d", n - ans);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1140 KB Output is correct
2 Correct 45 ms 1140 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1140 KB Output is correct
2 Correct 55 ms 1140 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1140 KB Output is correct
2 Correct 40 ms 1140 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1140 KB Output is correct
2 Correct 53 ms 1140 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1140 KB Output is correct
2 Correct 55 ms 1140 KB Output is correct