Submission #1064710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064710		sammyuri	Painting Walls (APIO20_paint)	C++17	100 / 100	267 ms	17332 KiB

paint

#include "paint.h"

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

bool ee[100005];
int rem[50005];

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<vector<int>> allowed(K);
    for (int i = 0; i < M; i ++) {
        for (auto a : B[i])
            allowed[a].push_back(i);
    }
    int bigmod = M;
    while (bigmod <= N)
        bigmod += M;

    memset(rem, 0, sizeof(rem));
    int goodcnt = 0;
    for (int i = 0; i < N; i ++) {
        for (auto a : allowed[C[i]]) {
            int cc = (a - i + bigmod) % M;
            rem[cc] ++;
            if (rem[cc] == M)
                goodcnt ++;
        }
        if (i >= M) {
            // remove previous ones
            for (auto a : allowed[C[i - M]]) {
                int cc = (a - i + bigmod) % M;
                if (rem[cc] == M)
                    goodcnt --;
                rem[cc] --;
            }
        }
        if (goodcnt > 0)
            ee[i] = true;
        else
            ee[i] = false;
    }

    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: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37