제출 #1197405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197405		adiyer	벽 칠하기 (APIO20_paint)	C++20	0 / 100	1598 ms	153052 KiB

paint

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 11;

int n, m;
int c[MAXN], dp[MAXN];

map < int, int > was[MAXN];

bool check(int s, int l){
    for(int i = s; i < s + m; i++){
        if(!was[i % m][c[l]]) return 0;
        l++;
    }
    return 1;
}

int minimumInstructions(int N, int M, int K, vector < int > C, vector < int > A, vector < vector < int > > B) {
    n = N, m = M;
    for(int i = 0; i < n; i++) c[i] = C[i], dp[i] = MAXN;
    for(int i = 0; i < M; i++)
        for(int x : B[i])
            was[i][x] = 1;
    for(int x = 0; x < m; x++){
        if(check(x, 0)){
            for(int i = 0; i < m; i++) dp[i] = 1;
            break;
        }
    }
    for(int i = m; i < n; i++){
        for(int x = 0; x < m; x++){
            if(check(x, i - m + 1)){
                dp[i] = min(dp[i], dp[i - m] + 1);
                break;
            }
        }
    }
    if(dp[n - 1] == MAXN) return -1;
    else return dp[n - 1]; 
}

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