oj.uz

Submission #276922

# Submission time Handle Problem Language Result Execution time Memory
276922 2020-08-20T18:59:30 Z wutwere Studentsko (COCI14_studentsko) C++17
100 / 100
 162 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, k; cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n ; i++)
		cin >> v[i];
	vector<int> sortedv = v;
	sort(sortedv.begin(), sortedv.end());
	for (int i = 0; i < n / k; i++) {
		set<int> s;
		for (int j = 0; j < k; j++) {
			s.insert(sortedv[i * k + j]);
		}
		int p = 0;
		for (int j = 0; j < n; j++) {
			if (s.count(v[j])) {
				v[j] = sortedv[i * k + p];
				p++;
			}
		}
	}
	vector<int> dp(n, 1);
	int longest = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (v[i] > v[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		longest = max(longest, dp[i]);
	}
	cout << n - longest;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 384 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 384 KB Output is correct
2 Correct 73 ms 384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 384 KB Output is correct
2 Correct 162 ms 384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 384 KB Output is correct
2 Correct 26 ms 512 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 384 KB Output is correct
2 Correct 49 ms 460 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 488 KB Output is correct
2 Correct 45 ms 384 KB Output is correct