답안 #394238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394238	2021-04-26T08:08:10 Z	thuanqvbn03	벽 칠하기 (APIO20_paint)	C++17	컴파일 오류	0 ms	0 KB

paint

const int MAX_N = 200005;
const int INF = 1000000000;

int pre[MAX_N], nex[MAX_N];
int mark[MAX_N], dp[MAX_N];
int prefixSum[MAX_N];
deque<int> q;

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b)
{
    for (int i = 0; i < n; i++)
    {
        nex[i] = -1;
        for (int j = 0; j < m && i + j < n; j++)
        {
            if (binary_search(b[j].begin(), b[j].end(), c[i + j]))
            {
                nex[i] = i + j;
            }
            else
            {
                break;
            }
        }
        if (nex[i] - i + 1 == m)
        {
            mark[i] = true;
        }
    }
    for (int i = 0; i < n; i++)
    {
        pre[i] = -1;
        for (int j = i; j >= 0 && i - j < m; j--)
        {
            if (binary_search(b[m - (i - j + 1)].begin(), b[m - (i - j + 1)].end(), c[j]))
            {
                pre[i] = j;
            }
            else
            {
                break;
            }
        }
    }
    for (int i = 1; i < n; i++)
    {
        if (pre[i - 1] == -1 || nex[i] == -1)
        {
            continue;
        }
        if (nex[i] - pre[i - 1] + 1 < m)
        {
            continue;
        }
        prefixSum[pre[i - 1]]++;
        prefixSum[nex[i] - m + 2]--;
    }
    for (int i = 0; i < n; i++)
    {
        if (prefixSum[i])
        {
            mark[i] = true;
        }
        prefixSum[i + 1] += prefixSum[i];
    }
    if (!mark[0] || !mark[n - m])
    {
        return -1;
    }
    dp[0] = 1;
    q.push_back(0);
    for (int i = 1; i <= n - m; i++)
    {
        if (mark[i])
        {
            while (q.size() && q.front() < i - m)
            {
                q.pop_front();
            }
            if (q.empty())
            {
                return -1;
            }
            dp[i] = dp[q.front()] + 1;
            while (q.size() && dp[q.back()] >= dp[i])
            {
                q.pop_back();
            }
            q.push_back(i);
        }
    }
    return dp[n - m];
}

Compilation message

paint.cpp:7:1: error: 'deque' does not name a type
    7 | deque<int> q;
      | ^~~~~
paint.cpp:9:46: error: 'vector' has not been declared
    9 | int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b)
      |                                              ^~~~~~
paint.cpp:9:52: error: expected ',' or '...' before '<' token
    9 | int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b)
      |                                                    ^
paint.cpp: In function 'int minimumInstructions(int, int, int, int)':
paint.cpp:16:31: error: 'b' was not declared in this scope
   16 |             if (binary_search(b[j].begin(), b[j].end(), c[i + j]))
      |                               ^
paint.cpp:16:57: error: 'c' was not declared in this scope
   16 |             if (binary_search(b[j].begin(), b[j].end(), c[i + j]))
      |                                                         ^
paint.cpp:16:17: error: 'binary_search' was not declared in this scope
   16 |             if (binary_search(b[j].begin(), b[j].end(), c[i + j]))
      |                 ^~~~~~~~~~~~~
paint.cpp:35:31: error: 'b' was not declared in this scope
   35 |             if (binary_search(b[m - (i - j + 1)].begin(), b[m - (i - j + 1)].end(), c[j]))
      |                               ^
paint.cpp:35:85: error: 'c' was not declared in this scope
   35 |             if (binary_search(b[m - (i - j + 1)].begin(), b[m - (i - j + 1)].end(), c[j]))
      |                                                                                     ^
paint.cpp:35:17: error: 'binary_search' was not declared in this scope
   35 |             if (binary_search(b[m - (i - j + 1)].begin(), b[m - (i - j + 1)].end(), c[j]))
      |                 ^~~~~~~~~~~~~
paint.cpp:71:5: error: 'q' was not declared in this scope
   71 |     q.push_back(0);
      |     ^