Submission #1058358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058358		mispertion	Painting Walls (APIO20_paint)	C++17	100 / 100	230 ms	253476 KiB

paint

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

using namespace std;

const int N = 1e5 + 10;

#define sz(x) (int)x.size()
#define pb push_back

int n, m, k, ok[N];
vector<int> c, a;
vector<vector<int>> pos, b;
vector<int> dp[N];

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, vector<vector<int>> B) {
    n = N;
    m = M;
    k = K;
    c = C;
    a = A;
    b = B;
    pos.resize(k);
    for(int i = 0; i < m; i++){
        for(auto e : b[i])
            pos[e].pb(i);
    }
    for(int i = 0; i < n; i++){
        dp[i].assign(sz(pos[c[i]]), 1);
        if(sz(dp[i]) == 0)
            return -1;
    }
    if(m == 1)
        return n;
    for(int i = n - 2; i >= 0; i--){
        int ru = 0;
        for(int lu = 0; lu < sz(dp[i]); lu++){
            while(ru < sz(dp[i + 1]) && pos[c[i + 1]][ru] <= pos[c[i]][lu])
                ru++;
            if(ru == sz(dp[i + 1]) || pos[c[i]][lu] + 1 < pos[c[i + 1]][ru])
                continue;
            dp[i][lu] = dp[i + 1][ru] + 1;
        }
        if(pos[c[i]][sz(dp[i]) - 1] == m - 1 && pos[c[i + 1]][0] == 0)
            dp[i][sz(dp[i]) - 1] = dp[i + 1][0] + 1;
        for(auto e : dp[i]){
            if(e >= m)
                ok[i] = 1;
        }
    }
    int ans = 0, r = 0;
    while(r < n){
        int nr = -1;
        for(int l = 0; l < m; l++){
            if(r - l < 0)
                break;
            if(ok[r - l]){
                nr = r - l + m;
                break;
            }
        }
        if(nr == -1)
            return -1;
        ans++;
        r = nr;
    }
    return ans;
}

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