Submission #546262

#	Time	Username	Problem	Language	Result	Execution time	Memory
546262		cig32	Painting Walls (APIO20_paint)	C++17	28 / 100	1610 ms	469900 KiB

paint

#include "paint.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <unordered_map>
using namespace std;
int minimumInstructions(int N, int M, int K, std::vector<int> C,std::vector<int> A, std::vector<std::vector<int>> B) {
  int dp[N];
  for(int i=0; i<N; i++) dp[i] = 1e9;
  unordered_map<int,bool> contains[M];
  for(int i=0; i<M; i++) {
    for(int j=0; j<B[i].size(); j++) {
      contains[i][B[i][j]] = 1;
    }
  }
  int val[N][M]; // val[i][j] := maximum chain if i choose contractor j at position i
  for(int i=0; i<N; i++) for(int j=0; j<M; j++) val[i][j] = -1e9;
  for(int i=N-1; i>=0; i--) {
    for(int j=0; j<M; j++) {
      if(contains[j][C[i]]) {
        val[i][j] = max(val[i][j], (i+1 == N ? 0 : max(0, val[i+1][(j+1) % M])) + 1);
      }
      else {
        val[i][j] = -1e9;
      }
    }
  }
  int mxchain[N];
  for(int i=0; i<N; i++) {
    mxchain[i] = -1e9;
    for(int j=0; j<M; j++) {
      mxchain[i] = max(mxchain[i], val[i][j]);
    }
  }
  for(int i=M-1; i<N; i++) {
    if(mxchain[i-M+1] >= M) {
      for(int j=i-M; j<i; j++) {
        dp[i] = min(dp[i], (j<0 ? 0 : dp[j]) + 1);
      }
    }
  }
  return (dp[N-1] > 1e8 ? -1 : dp[N-1]);
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int j=0; j<B[i].size(); j++) {
      |                  ~^~~~~~~~~~~~

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