# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
492340 | aris12345678 | Studentsko (COCI14_studentsko) | C++14 | 2 ms | 332 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define X first
#define Y second
const int mxN = 5005;
pii v[mxN];
int main() {
int n, k;
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++) {
scanf("%d", &v[i].X);
v[i].Y = i;
}
sort(v, v+n);
vector<int> pos(n);
for(int i = 0; i < n; i++)
pos[v[i].Y] = i/k;
vector<int> dp;
for(int i = 0; i < n; i++) {
if(dp.empty())
dp.push_back(pos[i]);
else if(dp[int(dp.size()-1)] <= pos[i])
dp.push_back(pos[i]);
else {
int p = lower_bound(dp.begin(), dp.end(), pos[i])-dp.begin();
dp[p] = pos[i];
}
}
printf("%d\n", n-int(dp.size()));
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |