Submission #1219184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219184		Mans21	Painting Walls (APIO20_paint)	C++20	28 / 100	1592 ms	1664 KiB

paint

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

using namespace std;

const int maxn = 100'000 + 12;

bool is[maxn];

int minimumInstructions(
    int n, int m, int k, vector<int> c, vector<int> A, vector<vector<int>> B) {

    for(int i = 0; i < m; i++) {
        sort(B[i].begin(), B[i].end());
    }

    auto check = [&](int i, int x) -> bool {
        auto it = lower_bound(B[i].begin(), B[i].end(), x);
        return it != B[i].end() && *it == x;
    };

    for(int x = 0; x < m; x++) {
        for(int y = 0; y <= n - m; y++) {
            bool fg = true;
            for(int l = 0; l < m; l++) {
                fg &= check((x + l) % m, c[y + l]);
            }
            is[y] |= fg;
        }
    }

    int ans = 0, last = -1e9, cur = -1e9;
    for(int i = 0; i < n; i++) {
        if(is[i]) last = i;
        if(i - cur >= m) {
            if(i - last >= m) {
                return -1;
            }
            cur = last;
            ans++;
        }
    }
    return ans;
}

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