제출 #1312081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312081		maya_s	벽 칠하기 (APIO20_paint)	C++20	28 / 100	1502 ms	8976 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll inf = 1e9;

bool ok(ll start, int m, int k, vector<int> &c, vector<int> &a, vector<set<int>> &s){
  for(ll shift = 0; shift < m; shift++){
    bool lol = 1;
    for(ll i = start; i < start + m && lol; i++){
      if(s[(i + shift) % m].find(c[i]) == s[(i + shift) % m].end()) lol = 0;
    }
    if(lol) return 1;
  }
  return 0;
}

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
  vector<ll> dp(n, inf); 
  vector<set<ll>> s(m);
  for(ll i = 0; i < m; i++) for(ll j: b[i]) s[i].insert(j);
  dp[m-1] = (ok(0, m, k, c, a, s) ? 1 : inf);
  for(ll i = m; i < n; i++) {
    if(ok(i-m+1, m, k, c, a, s)){
      for(ll j = i-1; j >= i-m; j--) dp[i] = min(dp[i], dp[j]+1);
    }
  }
  return dp[n-1] != inf ? dp[n-1] : -1;
}

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