Submission #788610

#	Time	Username	Problem	Language	Result	Execution time	Memory
788610		WLZ	Painting Walls (APIO20_paint)	C++17	100 / 100	1107 ms	17212 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector< vector<int> > B) {
  vector< vector<int> > occ(K);
  for (int i = 0; i < M; i++) {
    for (auto& x : B[i]) {
      occ[x].push_back(i);
    }
  }

  auto prev = [&](const int &x, const int &i) {
    return ((x - i) % M + M) % M;
  };

  vector<int> cnt(M, 0);
  for (int i = 0; i < M; i++) {
    for (auto& x : occ[C[i]]) {
      cnt[prev(x, i)]++;
    }
  }
  vector<bool> a(N, false);
  for (int i = 0; i < M; i++) {
    if (cnt[i] == M) {
      a[0] = true;
    }
  }
  for (int i = M; i < N; i++) {
    for (auto& x : occ[C[i - M]]) {
      cnt[prev(x, i % M)]--;
    }
    for (auto& x : occ[C[i]]) {
      if (++cnt[prev(x, i % M)] == M) {
        a[i - M + 1] = true;
      }
    }
  }
  if (!a[N - M]) {
    return -1;
  }
  vector<int> dp(N, INF);
  dp[N - M] = 1;
  multiset<int> st;
  for (int i = 0; i < M - 1; i++) {
    st.insert(INF);
  }
  st.insert(1);
  for (int i = N - M - 1; i >= 0; i--) {
    if (a[i]) {
      dp[i] = min(dp[i], *st.begin() + 1);
    }
    st.erase(st.lower_bound(dp[i + M]));
    st.insert(dp[i]);
  }
  if (dp[0] == INF) {
    return -1;
  }
  return dp[0];
}

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