제출 #1176516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176516		Muhammet	벽 칠하기 (APIO20_paint)	C++20	100 / 100	580 ms	292476 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));
    for(int i = 0; i < (int)v[c[n-1]].size(); i++) {
        d[n-1][i] = 1;
    }
    for(int i = n-2; i >= 0; i--) {
        int ind = 0;
        for(int j = 0; j < (int)v[c[i]].size(); j++) {
            int x = v[c[i]][j];
            d[i][j] = 1;
            while(ind < (int)v[c[i+1]].size() and x >= v[c[i+1]][ind]) {
                ind++;
            }
            if(ind < (int)v[c[i+1]].size() and v[c[i+1]][ind] == x+1) d[i][j] = d[i+1][ind] + 1;
        }
    }
    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(!(int)v[c[y]].size() or v[c[y]][0]) continue;
            if(d[i][j] + i >= y and d[y][0] + y >= x) e[i] = true;
        }
    }
    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: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37