Submission #1214071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214071		dzuizz	Painting Walls (APIO20_paint)	C++20	28 / 100	1618 ms	488600 KiB

paint

// Subtask 4
#include "paint.h"
#include <vector>
#include <map>
#include <cstring>
#include <iostream>
using namespace std;
int n,m,k;
int minimumInstructions(int _n,int _m,int _k,vector<int>c,std::vector<int>a,std::vector<std::vector<int>>b) {
  n=_n,m=_m,k=_k;

  map<int,bool> mp[m];
  for(int i=0;i<m;++i)
    for(auto&x:b[i]) mp[i][x]=1;

  int dp[n][m];
  for(int i=n-1;i>=0;--i){
    for(int j=0;j<m;++j){
      dp[i][j]=mp[j][c[i]];
      if(i<n-1&&dp[i][j]) dp[i][j]+=dp[i+1][(j+1)%m];
    }
  }
  bool can[n]; memset(can,0,sizeof can);
  for(int i=0;i<n;++i) for(int j=0;j<m;++j)
    can[i]=can[i]||(dp[i][j]>=m);

  for(int i=0;i<n;++i) cerr<<can[i]<<" "; cerr<<'\n';

  int ans=0,i=0,j=can[0]?m:0,nj;
  while(i<j){
    cerr<<i<<" "<<j<<'\n';
    for(nj=0;i<n&&i<j;++i)
      if(can[i]) nj=i+m;
    if(i<n&&can[i]) j=i+m;
    else j=nj;
    ++ans;
  }
  return i==n?ans:-1;
}

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