Submission #394239

#	Time	Username	Problem	Language	Result	Execution time	Memory
394239		thuanqvbn03	벽 칠하기 (APIO20_paint)	C++17	100 / 100	556 ms	9340 KiB

paint

#include <bits/stdc++.h>

using namespace std;

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];
}

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