Submission #1274674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274674		Robert_junior	Painting Walls (APIO20_paint)	C++20	0 / 100	658 ms	589824 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int minimumInstructions(int n, int m, int k, std::vector<int> c, std::vector<int> a, std::vector<std::vector<int>> b) {
    vector<int>used(n), dp(n, n + 1);
    bitset<100010>is[m];
    for(int i = 0; i < m; i++){
        for(auto it : b[i]){
            is[i][it] = 1;
        }
    }
    for(int i = 0; i < m; i++){
        int o = i, oo = 0;
        while(oo < m && is[o][c[oo]]){
            oo++;
            o = (o + 1) % m;
        }
        if(oo == m){
            for(int j = 0; j < m; j++) dp[j] = 1;
        }
    }
    for(int i = 1; i <= n - m; i++){
        for(int j = 0; j < m; j++){
            int o = j, oo = i;
            while(oo < i + m && is[o][c[oo]]){
                oo++;
                o = (o + 1) % m;
            }
            if(oo == i + m){
                for(int l = i; l < i + m; l++){
                    dp[l] = min(dp[l], dp[i - 1] + 1);
                }
            }
        }
    }
    if(dp[n - 1] >= n + 1) dp[n - 1] = -1;
    return dp[n - 1];
}

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