Submission #961570

#	Time	Username	Problem	Language	Result	Execution time	Memory
961570		kilkuwu	Painting Walls (APIO20_paint)	C++17	100 / 100	333 ms	15004 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

int minimumInstructions(int N, int M, int K, std::vector<int> C,
                        std::vector<int> A, std::vector<std::vector<int>> B) {

  
  // what can we do now

  std::vector<std::vector<int>> colors(K);
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < A[i]; j++) {
      colors[B[i][j]].push_back(i);
    }
  }

  std::vector<std::pair<int, int>> good;

  for (int j = 0; j < (int) colors[C[N - 1]].size(); j++) {
    good.emplace_back(colors[C[N - 1]][j], 1);
  }

  std::vector<int> ok(N);
  ok[N - 1] = (colors[C[N - 1]].size() > 0) >= M;

  for (int i = N - 2; i >= 0; i--) {

    int r = 0;
    std::vector<std::pair<int, int>> new_good;
    int best = 0;

    for (int l = 0; l < (int) colors[C[i]].size(); l++) {
      while (r < (int) good.size() && good[r].first <= colors[C[i]][l]) {
        r++;
      }

      if (r < (int) good.size() && good[r].first == colors[C[i]][l] + 1) {
        best = std::max(best, good[r].second + 1);
        new_good.emplace_back(colors[C[i]][l], good[r].second + 1);
      } else {
        if (l != (int) colors[C[i]].size() - 1) {
          best = std::max(best, 1);
          new_good.emplace_back(colors[C[i]][l], 1);
        } else {
          if (good.size() && good[0].first == 0 && colors[C[i]][l] == M - 1) {
            best = std::max(best, good[0].second + 1);
            new_good.emplace_back(colors[C[i]][l], good[0].second + 1);
          } else {
            best = std::max(best, 1);
            new_good.emplace_back(colors[C[i]][l], 1);
          }
        }
      }
    }

    std::swap(new_good, good);

    ok[i] = best >= M;
  }


  const int inf = 1e9 + 7;
  std::vector<int> dp(N + 1);
  dp[N] = 0;
  std::deque<int> dq;
  dq.push_back(N);

  for (int i = N - 1; i >= 0; i--) {
    if (!ok[i]) {
      dp[i] = inf;
    } else {
      while (dq.size() && dq.front() > i + M) dq.pop_front();
      if (dq.size()) {
        dp[i] = dp[dq.front()] + 1;
      } else {
        dp[i] = inf;
      }
    }

    while (dq.size() && dp[dq.back()] >= dp[i]) {
      dq.pop_back();
    }
    dq.push_back(i);
  }

  return dp[0] < inf ? dp[0] : -1;
}

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