제출 #1176506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176506		Muhammet	벽 칠하기 (APIO20_paint)	C++20	0 / 100	0 ms	324 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 <int> v[k+1];
    for(int i = 0; i < m; i++) {
        for(auto j : b[i]) {
            v[j].push_back(i);
        }
    }
    vector <vector <int>> d(n+2, vector <int> (705, 0));
    vector <int> ind0(n+1, -1);
    unordered_map <int, int> dp, dp1;
    for(int i = 0; i < (int)v[c[n-1]].size(); i++) {
        int x = v[c[n-1]][i];
        if(x == 0) ind0[n-1] = i;
        dp[x] = 1;
    }
    for(int i = n-2; i >= 0; i--) {
        for(int j = 0; j < (int)v[c[i]].size(); j++) {
            int x = v[c[i]][j];
            if(x == 0) ind0[i] = j;
            d[i][j] = dp[x+1] + 1;
            dp1[x] = dp[x+1] + 1;
        }
        dp = dp1;
        dp1.clear();
        // 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 < (int)v[c[i]].size(); j++) {
    //         int x = v[c[i]][j];
    //         cout << x << ' ' << d[i][j] << "\n";
    //     }
    // }
    vector <bool> e(n+1, 0);
    for(int i = 0; i < n - m + 1; i++) {
        for(int j = 0; j < (int)v[c[i]].size(); j++) {
            int x = i + m, y = i + m - v[c[i]][j];
            if(!v[c[i]][j] and d[i][j] + i >= x) e[i] = true;
            if(ind0[y] == -1) continue;
            if(d[i][j] + i >= y and d[y][ind0[y]] + y >= x) e[i] = true;
        }
        // cout << e[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--;
        // }
    }
    vector <int> v1;
    for(int i = 0; i < n; i++) {
        if(e[i]) v1.push_back(i);
    }
    if(!e[0]) return -1;
    int ans = 1, y = 0;
    while(y < n - m) {
        bool tr = 0;
        int t = upper_bound(v1.begin(), v1.end(), y + m) - v1.begin() - 1;
        if(t < 0 or y == v1[t]) return -1;
        y = v1[t];
        ans++;
    }
    return ans;
}

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