Submission #714575

#	Time	Username	Problem	Language	Result	Execution time	Memory
714575		MDSPro	Painting Walls (APIO20_paint)	C++14	28 / 100	1579 ms	9684 KiB

paint

#include "paint.h"

#include <iostream>
#include <vector>
#include <set>
using namespace std;

const int INF = 1e9;
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    // [y,y+M-1]
    vector<set<int>> BB;
    for(auto z: B) {
        BB.emplace_back(set<int>(z.begin(),z.end()));
    }

    vector<pair<int,int>> segs;
    for(int y = 0; y <= N-M; ++y){
        for(int x = 0; x < M; ++x){
            bool ok = true;
            for(int l = 0; l < M; ++l){
                if(BB[(x+l)%M].count(C[y+l]) == 0) {
                    ok = false;
                    break;
                }
            }

            if(ok) segs.emplace_back(y,y+M-1);
        }
    }

    vector<int> dp(N,INF);
    for(auto z: segs){
        int l = z.first, r = z.second;
        // cerr << '[' << l << ',' << r << ']' << '\n';
        if(l == 0) dp[r] = 1;
        else {
            for(int d = l-1; d < r; ++d){
                if(dp[d] != INF) dp[r] = min(dp[d]+1,dp[r]);
            }
        }
    }

    if(dp[N-1] == INF) return -1;
    else return dp[N-1];
};

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