Submission #298661

#	Time	Username	Problem	Language	Result	Execution time	Memory
298661		Bruteforceman	Painting Walls (APIO20_paint)	C++11	100 / 100	564 ms	15608 KiB

paint

#include "bits/stdc++.h"
#include "paint.h"
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 1e9;
vector <int> col[maxn];
int opt[2][maxn];

int c[maxn];
int n, m;
bool good[maxn];
int dp[maxn];

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
  n = N;
  m = M;
  for(int i = 0; i < n; i++) {
    c[i] = C[i];
  }
  for(int i = 0; i < m; i++) {
    for(int j : B[i]) {
      col[j].push_back(i);
    }
  }
  int row = 0;
  for(int i = n - 1; i >= 0; i--) {
    good[i] = false;
    row ^= 1;
    for(int j : col[c[i]]) {
      opt[row][j] = opt[row ^ 1][(j + 1) % m] + 1;
      if(opt[row][j] >= m) good[i] = true;
    }
    if(i < n - 1) {
      for(int j : col[c[i + 1]]) {
        opt[row ^ 1][j] = 0;
      }
    }
  }
  for(int i = 0; i < n; i++) dp[i] = inf;
  dp[n] = 0;
  deque <pair <int, int>> Q;
  Q.push_front(make_pair(dp[n], n));
  for(int i = n; i >= 0; i--) {
    while(!Q.empty() && Q.back().second > i + m) {
      Q.pop_back();
    }
    if(good[i]) {
      dp[i] = 1 + Q.back().first;
    }
    while(!Q.empty() && Q.front().first >= dp[i]) {
      Q.pop_front();
    }
    Q.push_front(make_pair(dp[i], i));
  }
  return dp[0] >= inf ? -1 : dp[0];
}

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