Submission #861270

#	Time	Username	Problem	Language	Result	Execution time	Memory
861270		Dec0Dedd	Painting Walls (APIO20_paint)	C++14	100 / 100	235 ms	17828 KiB

paint

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

using namespace std;

const int N = 1e5+10;
const int INF = 1e9;
const int K = 1e5+10;

int ans[N], n, m, k;
vector<int> cl[N];

int len[2][K+1];

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) {
        for (auto u : b[i]) cl[u].push_back(i), cl[u].push_back(i+m);
    }

    if (n == 1) {
        bool ok=false;
        for (auto u : b[0]) ok |= (u == c[0]);
        if (ok) return 1;
        return -1;
    }

    for (int i=0; i<m-1; ++i) ans[i]=INF;
    for (auto u : cl[c[0]]) len[0][u]=1;

    if (m == 1 && len[0][c[0]] >= 1) ans[0]=1;
    else ans[0]=INF;

    multiset<int> ms; ms.insert(ans[0]);
    for (int i=1; i<n; ++i) {
        int mx=0;

        int l=(i-1)&1, r=i&1;
        for (auto u : cl[c[i]]) {
            if (len[l][u-1] == 0) len[r][u]=1;
            else len[r][u]=len[l][u-1]+1;
            mx=max(mx, len[r][u]);
        }

        if (mx >= m) ans[i]=(*ms.begin())+1;
        else ans[i]=INF;

        if (mx >= m && i == m-1) ans[i]=1;
        if (i-m >= 0) ms.erase(ms.find(ans[i-m]));
        ms.insert(ans[i]);

        for (auto u : cl[c[i-1]]) len[l][u]=0;
    }

    if (ans[n-1] >= INF) return -1;
    return ans[n-1];
}

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