Submission #319488

#	Time	Username	Problem	Language	Result	Execution time	Memory
319488		VEGAnn	Painting Walls (APIO20_paint)	C++14	28 / 100	36 ms	8932 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int M = 210;
const int N = 510;
const int oo = 2e9;
gp_hash_table<int, bool> inside[M];
int f[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 = 0; i < m; i++) {
    for (int j = 0; j < A[i]; j++) {
        inside[i][B[i][j]] = 1;

//            cerr << B[i][j] << " ";
    }
//    cerr << '\n';
    }

    f[n] = 0;

    fill(f, f + n, oo);

    for (int i = n - m; i >= 0; i--){
        int mn = oo;

        for (int j = 1; j <= m; j++)
            mn = min(mn, f[i + j]);

        if (mn == oo) continue;

        for (int j = 0; j < m; j++){
            int now = j;
            bool ok = 1;

            for (int it = 0; it < m && ok; it++){
                if (inside[now].find(C[i + it]) == inside[now].end()){
                    ok = 0;
                    break;
                }

                now++;

                if (now == m) now = 0;
            }

            if (ok){
                f[i] = mn + 1;
                break;
            }
        }
    }

    return (f[0] == oo ? -1 : f[0]);
}

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