제출 #858344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
858344		ily2003	학생 (COCI14_studentsko)	C++14	100 / 100	2 ms	600 KiB

studentsko

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n,k,dp[5001];
pair<int,int> a[5001];
vector<int> vec;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i=0;i<n;i++) {
        cin >> a[i].f;
        a[i].s=i;
    }
    sort(a,a+n);
    for(int i=0;i<n;i++) dp[a[i].s]=i/k;
    for(int i=0;i<n;i++) {
        if(vec.empty() || dp[i]>=vec.back()) vec.push_back(dp[i]);
        else {
            int so=upper_bound(vec.begin(),vec.end(),dp[i])-vec.begin();
            vec[so]=dp[i];
        }
    }
    cout<<n-vec.size()<<'\n';
    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