Submission #864122

#	Time	Username	Problem	Language	Result	Execution time	Memory
864122		jk410	Painting Walls (APIO20_paint)	C++17	0 / 100	7 ms	8536 KiB

paint

#include "paint.h"
#include <vector>
using namespace std;
vector<int> Walls[100000];//색이 i인 벽들
int D[2000][20000];//일꾼 i가 벽 j를 칠할 수 있다면 D[(i-j)%M][j]=1
int minimumInstructions(int N, int M, int K, std::vector<int> C,std::vector<int> A, std::vector<std::vector<int>> B){
    for (int i=0; i<N; i++)
        Walls[C[i]].push_back(i);
    for (int i=0; i<M; i++){
        for (int j:B[i]){
            for (int k:Walls[j])
                D[(i-k+M)%M][k]=1;
        }
    }
    for (int i=0; i<M; i++){
        for (int j=1; j<N; j++)
            D[i][j]+=D[i][j-1];
    }
    vector<int> v;
    for (int i=M-1; i<N; i++){
        for (int j=0; j<M; j++){
            if (D[j][i]-(i<M?0:D[j][i-M])==M){
                v.push_back(i);
                break;
            }
        }
    }
    int ret=0,prev=-1;
    for (int i=0; i<(int)v.size(); i++){
        if (i==(int)v.size()-1||v[i+1]>prev+M){
            if (v[i]>prev+M)
                return -1;
            ret++;
            prev=v[i];
        }
    }
    if (prev!=N-1)
        return -1;
    return ret;
}

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