Submission #1159429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159429		antonn	Painting Walls (APIO20_paint)	C++20	100 / 100	432 ms	253204 KiB

paint

#include <bits/stdc++.h>

 
using namespace std;
   
 
#define ll long long
#define ld long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	vector<vector<int>> who(K);
	for (int i = 0; i < M; i += 1) {
		for (auto j : B[i]) {
			who[j].push_back(i);
		}
	}
	vector<vector<int>> dp(N);
	for (int i = 0; i < N; i += 1) {
		dp[i].resize(who[C[i]].size());
	}
	for (int i = 0; i < who[C[N - 1]].size(); i += 1) {
		dp[N - 1][i] = 1;
	}
	for (int i = N - 2; i >= 0; i -= 1) {
		int ptr = 0;
		for (int j = 0; j < who[C[i]].size(); j += 1) {
			dp[i][j] = 1;
			while (ptr < who[C[i + 1]].size() && who[C[i + 1]][ptr] <= who[C[i]][j]) {
				ptr += 1;
			}
			if (ptr < who[C[i + 1]].size() && who[C[i + 1]][ptr] == (who[C[i]][j] + 1) % M) {
				dp[i][j] = dp[i + 1][ptr] + 1;
			}
			if (who[C[i]][j] == M - 1 && who[C[i + 1]].size() > 0 && who[C[i + 1]][0] == 0) {
				dp[i][j] = dp[i + 1][0] + 1;
			}
		}
	}
	vector<int> longest(N);
	for (int i = 0; i < N; i += 1) {
		for (int j = 0; j < who[C[i]].size(); j += 1) {
			longest[i] = max(longest[i], dp[i][j]);
		}
	}

	vector<int> sol(N, 1e9);
	sol[N - M] = (longest[N - M] >= M ? 1 : 1e9);
	
	deque<int> dq;
	for (int i = N - 1; i >= N - M; i -= 1) {
		while (!dq.empty() && sol[dq.back()] >= sol[i]) {
			dq.pop_back();
		}
		dq.push_back(i);
	}
	for (int i = N - M - 1; i >= 0; i -= 1) {
		while (!dq.empty() && dq.front() > i + M) {
			dq.pop_front();
		}
		if (longest[i] >= M) {
			// for (int j = i; j <= i + M - 1; j += 1) {
			//     sol[i] = min(sol[i], sol[j + 1] + 1);
			// }
			
			if (!dq.empty()) {
				sol[i] = min(sol[i], sol[dq.front()] + 1);
			}
		}
		while (!dq.empty() && sol[dq.back()] >= sol[i]) {
			dq.pop_back();
		}
		dq.push_back(i);
	}
	if (sol[0] == 1e9) {
		return -1;
	}
	return sol[0];
}

/**
int32_t main() {
  if (1) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  }
  int N, M, K;
  cin >> N >> M >> K;
  vector<int> C(N);
  for (int i = 0; i < N; i += 1) {
		cin >> C[i];
	}
	vector<int> A(M);
	vector<vector<int>> B(M);
  for (int i = 0; i < M; i += 1) {
		cin >> A[i];
		B[i].resize(A[i]);
		for (int j = 0; j < A[i]; j += 1) {
			cin >> B[i][j];
		}
	}
	cout << minimumInstructions(N, M, K, C, A, B);
  return 0;
}
**/
/**
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4

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

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37