Submission #1175731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175731		Muhammet	Painting Walls (APIO20_paint)	C++20	51 / 100	714 ms	589824 KiB

paint

#include "bits/stdc++.h"
#include "paint.h"
// #include "grader.cpp"

using namespace std;

int minimumInstructions(
    int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
    vector <vector <bool>> vis(m+1, vector <bool> (k+1, 0));
    for(int i = 0; i < m; i++) {
        for(auto j : b[i]) {
            vis[i][j] = true;
        }
    }
    vector <vector <int>> d(n+2, vector <int> (m+2, 0));
    for(int i = n-1; i >= 0; i--) {
        for(int j = 0; j < m; j++) {
            if(vis[j][c[i]] == true) d[i][j] = d[i+1][j+1] + 1;
        }
    }
    // for(int i = 0; i < n; i++) {
    //     cout << i << '\n';
    //     for(int j = 0; j < m; j++) {
    //         cout << j << ' ' << d[i][j] << "\n";
    //     }
    // }
    vector <bool> e(n+1, 0);
    for(int i = 0; i < n - m + 1; i++) {
        int x = i + m - 1, cnt = m-1;
        if(i + d[i][0] > x) e[i] = true;
        for(int j = i + 1; j <= x; j++) {
            if(j + d[j][0] > x and i + d[i][cnt] >= j) e[i] = true;
            cnt--;
            // cout << i << ' ' << cnt << ' ' << j << ' ' << 0 << " " << (j + d[j][0] > x and i + d[i][--cnt] >= j) << '\n';
        }
        // cout << e[i] << ' ';
    }
    // cout << '\n';
    if(!e[0]) return -1;
    int ans = 1, y = 0;
    while(y < n - m) {
        bool tr = 0;
        for(int i = y + m; i > y; i--) {
            if(e[i]) {
                tr = 1;
                y = i;
                break;
            }
        }
        if(!tr) return -1;
        ans++;
    }
    return ans;
}

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