제출 #1269199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269199		jojeonghoon	벽 칠하기 (APIO20_paint)	C++20	40 / 100	41 ms	16456 KiB

paint

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <map>
#include <set>
using namespace std;

const int LM=100100;
int N,M,K;
vector<int> C, A;
vector<vector<int>>B, E;
int D[LM], w[LM], ch[LM];
vector<int> pr;

void F(int x, int color){
    int d=0;
    
    for(int i:E[color]){
        int t=(i-x+M+N)%M;
        ch[t]=1;
        d=max(++w[t], d);
    }
    D[x]=d;
    
    for(int i:pr) if(!ch[i]) w[i]=0;
    pr.clear();
    for(int i:E[color]){
        ch[i]=0;
        pr.push_back(i);
    }
}

int minimumInstructions(int N_, int M_, int K_, vector<int> C_, vector<int>A_, vector<vector<int>>B_){
    N=N_, M=M_, K=K_, C=C_, A=A_, B=B_;
    
    E.assign(K, {});
    
    for(int i=0; i<M; i++){
        for(int j=0; j<A[i]; j++){
            E[B[i][j]].push_back(i);
        }
    }
    
    for(int i=0; i<N; i++){
        F(i, C[i]);
        if(D[i]==0) return -1;
    }
    
    int k=0;
    
    for(int i=0; i<N; i++){
        k++;
        if(D[i] >= D[i+1]){
            if(D[i]<M) return -1;
            
            if(D[i+1] <= k%M){
                k = (k+M-1)/M*M;
            }
        }
    }
    
    return (k+M-1)/M;
}

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