Submission #1116005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116005		adaawf	Painting Walls (APIO20_paint)	C++17	100 / 100	138 ms	18256 KiB

paint

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int f[100005], g[100005], dd[100005], d[100005];
vector<int> bb[100005];
int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
    for (int i = 0; i <= k; i++) bb[i].clear();
    for (int i = 0; i < m; i++) {
        for (int w : b[i]) {
            bb[w].push_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        f[i] = dd[i] = 0;
        for (int w : bb[c[i]]) {
            int h = i - w;
            if (h < 0) continue;
            if (f[h] == w) {
                f[h]++;
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        g[i] = 0;
        for (int w : bb[c[i]]) {
            int h = i + m - w - 1;
            if (h >= n) continue;
            if (g[h] == m - w - 1) {
                g[h]++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int w : bb[c[i]]) {
            int h = i - w;
            if (h < 0) continue;
            if (f[h] >= w + 1) {
                if (w == m - 1 || (h != 0 && g[h - 1] >= m - w - 1)) {
                    dd[i] = 1;
                    break;
                }
            }
        }
    }
    set<pair<int, int>> s;
    s.insert({0, -1});
    for (int i = 0; i < n; i++) {
        d[i] = 1e9;
        if (dd[i] == 1) {
            d[i] = (*s.begin()).first + 1;
        }
        if (i >= m - 1) {
            if (i == m - 1) s.erase({0, -1});
            else s.erase({d[i - m], i - m});
        }
        s.insert({d[i], i});
    }
    if (d[n - 1] >= 1e8) return -1;
    return d[n - 1];
}

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