Submission #1202886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202886		ackhava	벽 칠하기 (APIO20_paint)	C++20	100 / 100	397 ms	12872 KiB

paint

#include "paint.h"
#pragma GCC optimize "O3,unroll-loops"
#pragma GCC target "abm,bmi,bmi2,popcnt,lzcnt,avx,avx2"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(v) begin(v), end(v)
#define REP(i,o,n) for(int i=o;i<n;i++)
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) {
  vector<bool> possible(N+20);
  vector<int> streak(N+20);
  vector<vector<int>> like(K+20);

  REP(i,0,M)for(auto j:B[i])like[j].pb(i);

  vector<int> active;

  REP(pos,0,N){
    vector<pair<int,int>> vec;
    for(auto i:like[C[pos]])vec.pb({i,streak[((i+M-1)%M)]+1});
    for(auto i:active)streak[i]=0;
    active.clear();
    for(auto i:vec)active.pb(i.fi),streak[i.fi]=i.se;
    for(auto i:vec){ 
      if(i.se >= M)possible[pos-M+1]=true;
    }
    // REP(i,0,M)cerr<<streak[i]<<' ';
    // cerr<<endl;
  }

  int lim=0;
  int nli=-1;
  int ans=0;
  REP(i,0,N){
    if(possible[i])nli=i+M;
    if(i==lim){
      if(nli <= lim)return -1;
      lim=nli;
      ans++;
    }
  }
  return ans;
}

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