oj.uz

Submission #396992

# Submission time Handle Problem Language Result Execution time Memory
396992 2021-05-01T04:42:29 Z mewnian Studentsko (COCI14_studentsko) C++14
100 / 100
 3 ms 464 KB 
#include <bits/stdc++.h>
#define sze(x) (ll)x.size()
#define idx(x, a) get<x>(a)
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;

const ll MAXN = 5e3 + 3;
const ll INF = 1e18 + 7;

ll a[MAXN], n, k, b[MAXN], res, lis[MAXN];

int main()
{
    ios_base::sync_with_stdio(0); cout.tie(0);
    #ifdef OFFLINE
    freopen("input.inp", "r", stdin);
    #endif
    cin >> n >> k;
    for (ll i = 1; i <= n; ++i) { cin >> a[i]; b[i] = a[i]; }
    sort(b + 1, b + n + 1); a[0] = -INF;
    for (ll i = 1; i <= n; ++i) a[i] = (lower_bound(b + 1, b + n + 1, a[i]) - b - 1) / k;
    fill(lis, lis + n + 1, INF); lis[0] = -INF;
    for (ll i = 1; i <= n; ++i)
    {
        ll r = upper_bound(lis, lis + n + 1, a[i]) - lis;
        res = max(res, r);
        lis[r] = a[i];
    }
    cout << n - res;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 464 KB Output is correct

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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