Submission #1021571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021571		MohamedFaresNebili	Painting Walls (APIO20_paint)	C++14	28 / 100	1587 ms	20220 KiB

paint

#include <bits/stdc++.h>
     
        using namespace std;

        int N, M, K;
        vector<int> C, A;
        vector<vector<int>> B;
        vector<int> adj[100005];
        map<int, int> Key[50005];
        int DP[100005];

        int solve(int i) {
            if(i >= N) return 0;
            if(DP[i] != -1) return DP[i];
            int best = 1e9 + 7; 
            for(auto u : adj[C[i]]) {
                bool ok = true;
                for(int l = 0; l < M; l++) {
                    int col = (u + l) % M;
                    ok &= (Key[col][C[i + l]] == 1);
                }
                if(!ok) continue;
                for(int l = 0; l < M; l++)
                    best = min(best, 1 + solve(i + l + 1));
            }
            return DP[i] = best;
        }

        int minimumInstructions(int _N, int _M, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B) {
            N = _N, M = _M, K = _K;
            swap(_C, C); swap(_A, A); swap(_B, B);
            for(int l = 0; l < N; l++) DP[l] = -1;
            for(int l = 0; l < M; l++) {
                for(int i = 0; i < A[l]; i++) {
                    adj[B[l][i]].push_back(l);
                    Key[l][B[l][i]] = 1;
                }
            }
            int res = solve(0);
            return (res == 1e9 + 7 ? -1 : res);
            return -1;
        }

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