Submission #1109928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109928		WH8	Studentsko (COCI14_studentsko)	C++14	100 / 100	3 ms	760 KiB

studentsko

#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define int long long
#define endl '\n'
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cout << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define flag cout << "HERE" << endl;
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);
#define prt(x) \
    cout << "Vector " << #x << endl << ":"; \
    for (auto it : x) cout << it << " "; \
    cout << endl;
#define ppr(x) \
    cout << "Pair " << #x << endl << ":";\
    cout << x.first << " " << x.second << endl;

int fwt[5005];
int n, k;

void upd(int p, int v){
	while (p <= n){
		fwt[p] = max(fwt[p], v);
		p += (p & (-p));
	}
}

int qrymx(int p){
	int ret = 0;
	while (p){
		ret = max(ret, fwt[p]);
		p -= (p & (-p));
	}
	return ret;
}

int32_t main(){
	FASTIO
	cin >> n >> k;
	vector<int> disc;
	int v[n+1]; iloop(1, n+1){
		int c; cin >> c;
		v[i] = c; 
		disc.pb(c);
	}
	sort(disc.begin(), disc.end());
	disc.erase(unique(disc.begin(), disc.end()), disc.end());
	iloop(1, n+1) v[i] = lower_bound(disc.begin(), disc.end(), v[i]) - disc.begin() + 1;
	iloop(1, n+1){
		if (v[i] % k == 0) v[i] = v[i] / k;
		else v[i] = v[i] / k + 1;
	}
	int longest = 0;
	iloop(1, n+1){
		int mx = qrymx(v[i]);
		longest = max(longest, mx + 1);
		upd(v[i], mx + 1);
	}
	cout << n - longest;
}

• 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