| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1089705 | raphaelp | 벽 칠하기 (APIO20_paint) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// #include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int nex(int x, int N)
{
return (x + 1) % N;
}
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B)
{
vector<int> dp(N, N + 1);
dp[0] = 0;
int buff2 = 1;
vector<vector<int>> colors(K);
for (int i = 0; i < M; i++)
{
for (int j = 0; j < A[i]; j++)
{
colors[B[i][j]].push_back(i);
}
}
deque<pair<int, int>> cur, next;
for (int i = 0; i < N; i++)
{
next.clear();
for (int j = 0; j < colors[C[i]].size(); j++)
{
while (!cur.empty() && cur.front().second <= colors[C[i]][j])
{
if (cur.front().second == colors[C[i]][j])
{
if (cur.front().first >= M - 1)
while (buff2 <= i + 1)
{
if (buff2 == N)
return dp[i - M + 1] + 1;
dp[buff2] = dp[i - M + 1] + 1;
buff2++;
}
if (nex(colors[C[i]][j], M))
next.push_back({cur.front().first + 1, nex(colors[C[i]][j], M)});
else
next.push_front({cur.front().first + 1, nex(colors[C[i]][j], M)});
}
cur.pop_front();
}
if (next.empty() || (next.back().second != nex(colors[C[i]][j], M) && next.front().second != nex(colors[C[i]][j], M)))
{
if (M == 1)
{
dp[i + 1] = dp[i] + 1;
}
if (nex(colors[C[i]][j], M))
next.push_back({1, nex(colors[C[i]][j], M)});
else
next.push_front({1, nex(colors[C[i]][j], M)});
}
}
swap(next, cur);
}
return -1;
}
int main()
{
int N, M, K;
cin >> N >> M >> K;
vector<int> A(M), C(N);
vector<vector<int>> B(M);
for (int i = 0; i < N; i++)
cin >> C[i];
for (int i = 0; i < M; i++)
{
cin >> A[i];
for (int j = 0; j < A[i]; j++)
{
B[i].push_back(0);
cin >> B[i][j];
}
}
cout << minimumInstructions(N, M, K, C, A, B);
}