Submission #665242

#	Time	Username	Problem	Language	Result	Execution time	Memory
665242		true22	Studentsko (COCI14_studentsko)	C++14	100 / 100	42 ms	512 KiB

studentsko

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10