oj.uz

Submission #965756

# Submission time Handle Problem Language Result Execution time Memory
965756 2024-04-19T06:59:57 Z Gromp15 Painting Walls (APIO20_paint) C++17
0 / 100
 1 ms 600 KB 
#include "paint.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

const int INF = 1e9;
int minimumInstructions(
    int n, int m, int k, std::vector<int> c,
    std::vector<int> a, std::vector<std::vector<int>> b) {
	vector<vector<int>> who(k), where(m);
	for (int i = 0; i < m; i++) for (int x : b[i]) who[x].emplace_back(i);
	for (int i = 0; i < n; i++) {
		for (int x : who[c[i]]) {
			where[((x - i) % m + m) % m].emplace_back(i);
		}
	}
	for (int i = 0; i < m; i++) {
		sort(all(where[i]));
		where[i].erase(unique(all(where[i])), where[i].end());
	}
	vector<bool> ok(n);
	for (int i = 0; i < m; i++) {
		int lst = -2, got = 0;
		for (int j : where[i]) {
			if (j - lst > 1) {
				got = 1, lst = j;
			}
			else got++, lst = j;
			if (got >= m) {
				ok[j - m + 1] = 1;
			}
		}
	}
	vector<int> dp(n + 1, INF);
	dp[0] = 0;
	multiset<int> good;
	vector<vector<int>> add(n+1), rem(n+1);
	for (int i = 0; i <= n; i++) {
		for (int x : add[i]) good.insert(x);
		for (int x : rem[i]) good.erase(good.find(x));
		if (good.size()) dp[i] = *good.begin();
		if (i < n && ok[i]) {
			add[i+1].emplace_back(dp[i] + 1);
			if (i + m + 1 <= n) rem[i+m+1].emplace_back(dp[i] + 1);
		}
	}
	return dp[n] == INF ? -1 : dp[n];
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -