Submission #1352306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1352306		po_rag526	Painting Walls (APIO20_paint)	C++20	0 / 100	1 ms	2628 KiB

paint

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

int minimumInstructions(
    int N, int M, int K,
    vector<int> C,
    vector<int> A,
    vector<vector<int>> B
) {
    vector<vector<int>> like(K);

    for (int j = 0; j < M; j++) {
        for (int c : B[j]) {
            like[c].push_back(j);
        }
    }

    vector<int> good(N, 0);

    for (int y = 0; y + M <= N; y++) {

        bool ok = false;

        for (int x = 0; x < M && !ok; x++) {

            bool valid = true;

            for (int l = 0; l < M; l++) {

                int contractor = (x + l) % M;
                int color = C[y + l];

                bool likeColor = false;

                for (int p : like[color]) {
                    if (p == contractor) {
                        likeColor = true;
                        break;
                    }
                }

                if (!likeColor) {
                    valid = false;
                    break;
                }
            }

            if (valid) ok = true;
        }

        if (ok) good[y] = 1;
    }

    int ans = 0;
    int i = 0;

    while (i < N) {

        bool painted = false;

        for (int y = max(0, i - M + 1); y <= i && y + M <= N; y++) {
            if (good[y]) {
                ans++;
                i = y + M;
                painted = true;
                break;
            }
        }

        if (!painted) return -1;
    }

    return ans;
}

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