Submission #678849

#	Time	Username	Problem	Language	Result	Execution time	Memory
678849		WebbWayne	Studentsko (COCI14_studentsko)	C++14	100 / 100	5 ms	468 KiB

studentsko

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define rep(i, a, b) for(int i = a; i < b; i++)
#define vi vector<int> 
#define ii pair<int, int>
#define pb push_back
#define f first
#define s second
#define all(i) (i).begin(), (i).end()
#define MOD 1000000007
#define endl '\n'

void solve(){
 
	ll n,k;
	cin >> n >> k;
 
	vector<ii> nums(n+1);
	rep(i, 1, n+1) {
		cin>>nums[i].f;
		nums[i].s = i;
	}

	sort(all(nums));

	//Now, we have their actual position with their index.
	vi actual(n+1);
	rep(i, 1, n+1) {
		actual[nums[i].s] = ((i+k-1)/k);
	}

	//Now actual is like 3, 1, 1, 2, 2, 3

	vi sub;
	sub.pb(actual[1]);
	rep(i, 2, n+1) {
		auto itr = upper_bound(sub.begin(), sub.end(), actual[i]);
		if(itr != sub.end()) {
			int ind = itr - sub.begin();
			sub[ind] = actual[i];
		}

		else 
			sub.pb(actual[i]);
	}

	cout<<n - sub.size()<<endl;
}
 
int main(){

 
	ll tc = 1;
	// cin >> tc;
	while(tc--) 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