oj.uz

Submission #387130

# Submission time Handle Problem Language Result Execution time Memory
387130 2021-04-08T03:12:15 Z milleniumEeee Painting Walls (APIO20_paint) C++17
0 / 100
 2 ms 1132 KB 
#include <bits/stdc++.h>
#include "paint.h"
//#include "grader.cpp"
using namespace std;

const int MAXN = (int)1e5 + 5;
const int INF = 1e9 + 7;

int pos[MAXN];
int dp[MAXN];
int pref[MAXN];

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	memset(pos, -1, sizeof(pos));
	for (int i = 0; i < M; i++) {
		for (int el : B[i]) {
			pos[el] = i;
		}
	}
	for (int i = 0; i < N; i++) {
		if (pos[C[i]] == -1) {
			return -1;
		}
	}
	auto nxt = [&](int p) {
		if (p + 1 < M) {
			return p + 1;
		} else {
			return 0;
		}
	};
	for (int i = 0; i + 1 < N; i++) {
		int before = (i > 0 ? pref[i - 1] : 0);
		pref[i] = before + (pos[C[i + 1]] == nxt(pos[C[i]]));
	}
		
	auto get = [&](int l, int r) {
		return pref[r - 1] - pref[l - 1];
	};
	auto can = [&](int l, int r) {
		if (r - l + 1 == M && get(l, r) == M - 1) {
			return true;
		} else {
			return false;
		}
	};
	fill(dp, dp + MAXN, INF);
	dp[0] = 0;
	for (int i = M - 1; i < N; i++) {
		if (can(i - M + 1, i)) {
			int best = INF;
			for (int j = i - M; j < i; j++) {
				if (j >= 0) {
					best = min(best, dp[j]);					
				}
			}
			dp[i] = best + 1;
		}
	}
	if (dp[N - 1] < INF) {
		return dp[N - 1];
	} else {
		return -1;
	}
}

/*
5 3 10
0 2 1 4 3
2 0 4
2 3 2
1 1
*/

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1132 KB Output isn't correct
2 Halted 0 ms 0 KB -