제출 #1225884

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225884		KALARRY	벽 칠하기 (APIO20_paint)	C++20	28 / 100	1601 ms	170940 KiB

paint

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int n,m,dp[100005],c[100005];
map<int,bool> likes[100005];

bool test_end(int i)
{
    int y = i - m + 1;
    if(y <= 0)
        return false;
    for(int x = 0 ; x < m ; x++)
    {
        bool problem = false;
        for(int l = 0 ; l < m ; l++)
        {
            int cur_x = (x+l)%m;
            int cur_y = y+l;
            if(!likes[cur_x][c[cur_y]])
            {
                problem = true;
                break;
            }
        }

        if(!problem)
            return true;
    }

    return false;
}

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;
    for(int i = N ; i >= 1 ; i--) //make it 1-indexed
        c[i] = C[i-1];
    for(int j = 0 ; j < M ; j++)
        for(auto x : B[j])
            likes[j][x] = true;
    dp[0] = 0;
    deque<int> avail;
    avail.push_back(0);
    for(int i = 1 ; i <= N ; i++)
    {
        dp[i] = -1;
        if(avail.empty())
            continue;
        if(i >= M+1 && avail.front() == dp[i-M-1])
            avail.pop_front();
        if(!test_end(i))
            continue;
        dp[i] = avail.front() + 1;
        while(avail.back() > dp[i])
            avail.pop_back();
        avail.push_back(dp[i]);
    }
    return dp[N];
}

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