#include "paint.h"
#include <iostream>
#include <vector>
using namespace std;
int n, m, k;
vector<int> c, a;
vector<vector<int>> b;
vector<vector<int>> getLikedBy() {
vector<vector<int>> ret(k);
for (int i = 0; i < m; i++) {
for (int j : b[i]) {
ret[j].push_back(i);
}
}
return ret;
}
int val(int i, int j, vector<vector<int>> &dp) {
return (i < n ? dp[i][j] : 0);
}
int solve(vector<vector<int>> &liked_by) {
// cout << "TF IS HAPPENING" << endl;
vector<vector<int>> dp(n);
for (int i = 0; i < n; i++) {
if (liked_by[c[i]].empty()) return -1;
dp[i].resize(i ? liked_by[c[i - 1]].size() + 1 : 1, 0);
}
if (n == 1) return 1;
// cout << "EIKHANE ASCHE?" << endl;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < liked_by[c[i]].size(); j++) {
dp[i].back() = max(dp[i].back(), 1 + val(i + 1, j, dp));
}
if (i == 0) continue;
int j_cur = 0, j_prv;
for (j_prv = 0; j_prv < liked_by[c[i - 1]].size(); j_prv++) {
while (j_cur < liked_by[c[i]].size() and liked_by[c[i]][j_cur] <= liked_by[c[i - 1]][j_prv]) j_cur++;
if (j_cur < liked_by[c[i]].size() and liked_by[c[i]][j_cur] == liked_by[c[i - 1]][j_prv] + 1) dp[i][j_prv] = 1 + val(i + 1, j_cur, dp);
}
if (liked_by[c[i]].front() == 0 and liked_by[c[i - 1]].back() == m - 1) dp[i][liked_by[c[i - 1]].size() - 1] = 1 + val(i + 1, 0, dp);
}
int ret = 0, start_at = (dp[0].back() >= m ? 0 : -1), needs_colour = 0;
for (int i = 0; i < n; i++) {
if (i == needs_colour) {
if (start_at == -1) return -1;
ret++;
start_at = -1;
needs_colour = start_at + m;
}
if (dp[i].back() >= m) start_at = i;
}
return ret;
}
int minimumInstructions(
int N, int M, int K, vector<int> C,
vector<int> A, vector<vector<int>> B) {
n = N, m = M, k = K;
c = C, a = A;
b = B;
vector<vector<int>> liked_by = getLikedBy();
return solve(liked_by);
}
Compilation message
paint.cpp: In function 'int solve(std::vector<std::vector<int> >&)':
paint.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int j = 0; j < liked_by[c[i]].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:40:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (j_prv = 0; j_prv < liked_by[c[i - 1]].size(); j_prv++) {
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | while (j_cur < liked_by[c[i]].size() and liked_by[c[i]][j_cur] <= liked_by[c[i - 1]][j_prv]) j_cur++;
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | if (j_cur < liked_by[c[i]].size() and liked_by[c[i]][j_cur] == liked_by[c[i - 1]][j_prv] + 1) dp[i][j_prv] = 1 + val(i + 1, j_cur, dp);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
