Submission #730657

#	Time	Username	Problem	Language	Result	Execution time	Memory
730657		t6twotwo	Painting Walls (APIO20_paint)	C++17	100 / 100	1135 ms	17184 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int inf = 1E6;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    auto F = [&](int x) {
        x %= M;
        if (x < 0) {
            x += M;
        }
        return x;
    };
    vector<vector<int>> f(K);
    for (int i = 0; i < M; i++) {
        for (int x : B[i]) {
            f[x].push_back(i);
        }
    }
    multiset<int> st;
    int good = 0;
    vector<int> dp(N + 1, inf), cnt(M);
    dp[0] = 0;
    for (int i = 0; i < M; i++) {
        st.insert(dp[i]);
        for (int j : f[C[i]]) {
            if (++cnt[F(j - i)] == M) {
                good++;
            }
        }
    }
    for (int i = M; i <= N; i++) {
        if (good) {
            dp[i] = min(dp[i], (*st.begin()) + 1);
        }
        if (i == N) {
            break;
        }
        st.erase(st.find(dp[i - M]));
        st.insert(dp[i]);
        for (int j : f[C[i - M]]) {
            if (cnt[F(j - i)]-- == M) {
                good--;
            }
        }
        for (int j : f[C[i]]) {
            if (++cnt[F(j - i)] == M) {
                good++;
            }
        }
    }
    return dp[N] == inf ? -1 : dp[N];
}

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