제출 #1193483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193483		omsincoconut	벽 칠하기 (APIO20_paint)	C++17	51 / 100	873 ms	589824 KiB

paint

/*
We just need to check for each length K segment whether there exist a way to color them or not.
*/

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = (int)1e9;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    vector<int> color_contractor[K];
    for (int i = 0; i < M; i++) {
        for (int j : B[i]) {
            color_contractor[j].push_back(i);
        }
    }

    int qc[M][N+1];
    for (int i = 0; i < M; i++) {
        fill(qc[i], qc[i]+N+1, 0);
    }

    for (int i = 0; i < N; i++) {
        for (int j : color_contractor[C[i]]) {
            qc[((j-i)%M+M)%M][i+1]++;
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            qc[j][i] += qc[j][i-1];
        }
    }

    int dp[N+1];
    fill(dp, dp+N+1, INF);
    dp[0] = 0;
    for (int i = 0; i+M <= N; i++) {
        bool can = false;
        for (int j = 0; j < M; j++) {
            can |= (qc[j][i+M] - qc[j][i] == M);
        }
        if (can) {
            for (int j = 1; j <= M; j++) {
                dp[i+j] = min(dp[i+j], dp[i]+1);
            }
        }
    }

    return (dp[N] == INF ? -1 : dp[N]);
}

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