Submission #1064641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064641		sammyuri	Painting Walls (APIO20_paint)	C++17	51 / 100	851 ms	15188 KiB

paint

#include "paint.h"

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

int check[20005];
bool ee[20005];

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
    
    memset(ee, false, sizeof(ee));
    vector<set<int>> allowed(K);
    for (int i = 0; i < M; i ++) {
        for (auto a : B[i])
            allowed[a].insert(i);
    }
    for (int i = 0; i < M; i ++) {
        memset(check, 0, sizeof(check));
        int cur = i;
        for (int j = 0; j < N; j ++) {
            if (!allowed[C[j]].count(cur)) {
                check[j] ++;
                check[min(N, j + M)] --;
            }
            cur = (cur + 1) % M;
        }
        for (int j = 1; j < N; j ++)
            check[j] += check[j - 1];
        for (int j = 0; j < N; j ++)
            ee[j] |= (check[j] == 0);
    }
    vector<int> dp(N + 1);
    dp[0] = 0;
    multiset<int> curmins;
    curmins.insert(0);
    for (int i = 1; i < M; i ++)
        dp[i] = 1e9, curmins.insert(1e9);
    for (int i = M; i <= N; i ++) {
        int best = 1e9;
        if (ee[i - 1]) {
            best = min(best, *curmins.begin() + 1);
        }
        dp[i] = best;
        curmins.erase(curmins.find(dp[i - M]));
        curmins.insert(best);
    }
    // for (auto a : dp)
    //     cout << a << " "; cout << endl;
    // for (int i = 0; i < N; i ++)
    //     cout << ee[i] << " "; cout << endl;
    if (dp[N] == 1e9)
        return -1;
    return dp[N];
}

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