Submission #1132925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132925		dombly	Painting Walls (APIO20_paint)	C++20	0 / 100	1 ms	396 KiB

paint

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

const int N = 1e5 + 10;
const int inf = 1e9;

using namespace std;

int dp[N];

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    for(int i = 1; i <= N; i++) dp[i] = inf;
    for(int i = 1; i <= N; i++) {
        vector<int>v;
        for(int j = i - M + 1; j <= i; j++) v.pb(C[j - 1]);
        bool k = false;
        for(int j = 0; j < M; j++) {
            bool ok = true;
            for(int k = 0; k < M; k++) {
                int nxt = (k + j) % M;
                bool have = false;
                for(int q = 0; q < A[nxt]; q++) if(B[nxt][q] == v[k]) have = true;
                if(!have) {
                    ok = false;
                    break;
                }
            }
            if(ok) k = true;
        }
        if(k) dp[i] = min(dp[i - M],dp[i - M + 1]) + 1;
    }
    /*for(int i = 1; i <= N; i++) cout << dp[i] << " ";
    cout << endl;*/
    return (dp[N] >= inf ? -1 : dp[N]);
}
/*
8 3 5
3 3 1 3 4 4 2 2
3
0 1 2
2
2 3
2
3 4

3

5 4 4
1 0 1 2 2
2
0 1
1
1
1
2
1
3

-1

*/

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