Submission #780759

#	Time	Username	Problem	Language	Result	Execution time	Memory
780759		aaron_dcoder	Studentsko (COCI14_studentsko)	C++17	100 / 100	3 ms	468 KiB

studentsko

#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) (static_cast<int>(0))
#define dbgv(VARN) (static_cast<int>(0))
#else 
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<<VARN << ", line: " << __LINE__ << "\n"
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
constexpr ll INFTY = 1e10;
#define var const auto&

int main() {
    ll N,K;
    cin >> N >> K;
    vector<ll> studskill(N);
    vector<pair<ll,ll>> skillist(N);
    for (ll i = 0; i < N; i++)
    {
        cin >> studskill[i];
        skillist[i] = {studskill[i],i};
    }

    sort(skillist.begin(),skillist.end());

    vector<ll> studteam(N,-1);
    for (ll i = 0; i < N; i++)
    {
        studteam[skillist[i].second] = i/K;
    }

    
    vector<ll> lastelem_best_LIS_with_len(N+1,INFTY);
    lastelem_best_LIS_with_len[0] = 0;

    for (ll i = 0; i < N; i++)
    {
        *upper_bound(lastelem_best_LIS_with_len.begin(),lastelem_best_LIS_with_len.end(),studteam[i])
        =studteam[i];
    }

    ll LIS_len = (lower_bound(lastelem_best_LIS_with_len.cbegin(),lastelem_best_LIS_with_len.cend(),INFTY)-lastelem_best_LIS_with_len.cbegin())-1;
    cout << N-LIS_len;
 
}

• 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