oj.uz

Submission #665242

# Submission time Handle Problem Language Result Execution time Memory
665242 2022-11-27T10:25:27 Z true22 Studentsko (COCI14_studentsko) C++14
100 / 100
 42 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

typedef pair<ll, ll> pl;
typedef vector<ll> vl;   
typedef vector<pl> vp;

#define nl "\n"
#define fr first
#define sc second
#define pb push_back

#define all(x) x.begin(), x.end()
#define fur(i, a, b) for(ll i = a; i <= b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= b; --i)
#define pv(x) for(auto k : x){cout << k << " ";} cout << nl
const ll inf = 1e17;

/*
    We are only concerned that the top k
    have to be the strongest and so on.
    We are NOT looking at their actual value, 
    as they can be jumbled up in their group
    We also know which elements have to be in which group
    Therefore, the actual identity of the elements in the
    group does not matter, as long as the group is made properly.
    Lol so we'll make the top k elements 1, then 2nd top k as 2
    and get a sequence. Then we'll get the longest >= sub. in nlogn

*/
void solve(){
    ll n, k;
    cin >> n >> k;
    pair<ll, ll> a[n+1];
    fur(i, 1, n){ 
        cin >> a[i].fr;
        a[i].sc = i;
    }
    sort(a+1, a+n+1);
    ll t = 0;
    vl b(n+1);
    ll num = 1;
    fur(i, 1, n){
        t++;
        b[a[i].sc] = num;
        if (t+1 > k){
            t = 0;
            num++;
        }
    }
   // pv(b);
    ll dp[n+1];
    dp[1] = 1;
    ll len = 0;
    fur(i, 2, n){
        dp[i] = 1;
        fur(j, 1, i-1){
            if (b[j] <= b[i]){
                dp[i] = max(dp[i], dp[j]+1);
                len = max(len, dp[i]);
            }
        }
    }
    cout << (n-len) << nl;
    
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll t = 1;
    //cin >> t;
    while(t--){
        
        solve();
    }
    
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 468 KB Output is correct
2 Correct 36 ms 484 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 492 KB Output is correct
2 Correct 41 ms 508 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 512 KB Output is correct
2 Correct 30 ms 484 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 468 KB Output is correct
2 Correct 39 ms 456 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 504 KB Output is correct
2 Correct 42 ms 496 KB Output is correct