Submission #546271

#	Time	Username	Problem	Language	Result	Execution time	Memory
546271		cig32	Painting Walls (APIO20_paint)	C++17	100 / 100	463 ms	15424 KiB

paint

#include "paint.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <map>
#include <deque>
#include <vector>
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;
  vector<int> contains[K]; // size of contains[i] = f(i)
  for(int i=0; i<M; i++) {
    for(int j=0; j<B[i].size(); j++) {
      contains[B[i][j]].push_back(i);
    }
  }
  int val[2][M];// val[i][j] := maximum chain if i choose contractor j at position i
  for(int i=0; i<2; i++) {
    for(int j=0; j<M; j++) {
      val[i][j] = 0;
    }
  }
  vector<int> edited[2];
  int mxchain[N];
  for(int i=0; i<N; i++) {
    mxchain[i] = -1e9;
  }
  for(int i=N-1; i>=0; i--) {
    for(int j: contains[C[i]]) {
      val[i & 1][j] = max(val[i & 1][j], val[(i+1) & 1][(j == M - 1 ? 0 : j + 1)] + 1);
      edited[i & 1].push_back(j);
      mxchain[i] = max(mxchain[i], val[i & 1][j]);
    }
    for(int j=0; j<edited[(i+1) & 1].size(); j++) {
      val[(i+1) & 1][edited[(i+1) & 1][j]] = 0;
    }
    edited[(i+1) & 1].clear();
  }
  deque<int> mono; 
  for(int i=M-1; i<N; i++) {
    while(mono.size() && mono[0] < i-M) {
      mono.pop_front();
    }
    if(mxchain[i-M+1] >= M) {
      dp[i] = (mono.empty() ? 0 : dp[mono[0]]) + 1;
    }
    while(mono.size() && dp[mono[mono.size() - 1]] >= dp[i]) {
      mono.pop_back();
    }
    mono.push_back(i);
  }
  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:15:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int j=0; j<B[i].size(); j++) {
      |                  ~^~~~~~~~~~~~
paint.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int j=0; j<edited[(i+1) & 1].size(); j++) {
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~

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