Submission #877565

#	Time	Username	Problem	Language	Result	Execution time	Memory
877565		boris_mihov	벽 칠하기 (APIO20_paint)	C++17	0 / 100	2 ms	8540 KiB

paint

#include "paint.h"
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n, m, k;
int a[MAXN];
int zeroLen[MAXN];
int lastLen[MAXN];
std::vector <int> canUse[MAXN];
std::unordered_set <int> canUseSet[MAXN];
bool isGood[MAXN];

int minimumInstructions(int N, int M, int K, std::vector <int> C, std::vector <int> A, std::vector <std::vector <int>> B)
{
    n = N; m = M; k = K;
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = C[i - 1] + 1;
    }

    for (int i = 0 ; i < m ; ++i)
    {
        for (int j = 0 ; j < A[i] ; ++j)
        {
            canUse[B[i][j] + 1].push_back(i + 1);
            canUseSet[B[i][j] + 1].insert(i + 1);
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = i ; j <= std::min(i + m - 1, n) ; ++j)
        {
            if (!canUseSet[a[j]].count(j - i + 1))
            {
                break;
            }

            zeroLen[i]++;
        }

        for (int j = i ; j >= std::max(i - m + 1, 1) ; --j)
        {
            if (!canUseSet[a[j]].count(m - (i - j)))
            {
                break;
            }

            lastLen[i]++;
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (const int &c : canUse[a[i]])
        {
            if (lastLen[i + m - c] >= m - c + 1 && zeroLen[i + m - c + 1] >= c - 1)
            {
                isGood[i] = true;
                break;
            }
        }
    }

    int ptr = 1;
    int ans = 0;
    int dest = 1;

    while (ptr <= n)
    {
        if (dest == 0) return -1;
        int newDest = 0;
        while (ptr <= dest)
        {
            if (isGood[ptr]) newDest = ptr + m;
            ptr++;
        }

        dest = newDest;
        ans++;
    }

    return ans;
}

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