제출 #1311409

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

paint

#include <bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define pb push_back
#define sz(x) (int)(x).size()

int minimumInstructions(int n, int m, int k, vi c, vi a, vector<vi> b) {
    vector<vector<int>> DP(n);
    vector<bool> F(n, false);
    vector<vector<int>> val(k);

    // build val[color] = list of positions in [0..m-1]
    for (int i = 0; i < m; ++i) {
        for (int x : b[i]) {
            val[x].pb(i);
        }
    }

    // base case i = n-1
    DP[n-1].resize(sz(val[c[n-1]]), 1);
    if (m == 1) F[n-1] = true;

    // DP from right to left
    for (int i = n - 2; i >= 0; --i) {
        DP[i].resize(sz(val[c[i]]));
        int best = 0;
        int ptr = 0;

        for (int idx = 0; idx < sz(val[c[i]]); ++idx) {
            int j = val[c[i]][idx];
            int need = (j + 1) % m;

            while (ptr < sz(val[c[i + 1]]) && val[c[i + 1]][ptr] < need)
                ++ptr;

            if (ptr == sz(val[c[i + 1]]) || val[c[i + 1]][ptr] != need) {
                DP[i][idx] = 1;
            } else {
                DP[i][idx] = DP[i + 1][ptr] + 1;
            }
            best = max(best, DP[i][idx]);
        }

        if (best >= m) F[i] = true;
    }

    // greedy cover
    int ans = 0;
    int l = 0, r = 0;

    while (r < n) {
        bool ok = false;
        while (r >= l) {
            if (F[r]) {
                ++ans;
                l = r + 1;
                r = r + m;
                ok = true;
                break;
            }
            --r;
        }
        if (!ok) return -1;
    }

    return ans;
}

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