Submission #1132974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132974		dombly	Painting Walls (APIO20_paint)	C++20	28 / 100	1595 ms	6984 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;
                if(!binary_search(B[nxt].begin(),B[nxt].end(),v[k])) {
                    ok = false;
                    break;
                }
            }
            if(ok) k = true;
        }
        if(k) {
            for(int j = i - M + 1; j <= i; j++) dp[i] = min(dp[i],dp[j - 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: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37