Submission #1166780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166780		epicci23	Painting Walls (APIO20_paint)	C++20	100 / 100	304 ms	13716 KiB

paint

#include "bits/stdc++.h"
#include "paint.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1e9 + 5;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
  int n = N,m = M,k = K;

  int ar[n+5];
  for(int i=1;i<=n;i++) ar[i] = C[i - 1];

  vector<int> rev[k + 5];
  for(int i=1;i<=m;i++){
  	for(int j = 0; j < A[i - 1]; j++){
  		int val = B[i - 1][j];
  		rev[val].push_back(i);
  		rev[val].push_back(i+m);
  	}
  }

  for(int i=0;i<=k;i++) sort(all(rev[i]));

  int doable[n+5],dp[n+5];
  memset(doable,0,sizeof(doable));

  vector<int> Old, New;
  Old.assign(sz(rev[ar[1]]),1);
  if(m == 1) doable[1] = 1;
 
  for(int i=2;i<=n;i++){
  	New.clear();
  	New.assign(sz(rev[ar[i]]),i);
  	int p = 0, maxi = 0;
    for(int j = 0; j < sz(rev[ar[i]]); j++){
      int u = rev[ar[i]][j];
      while(p < sz(Old) && rev[ar[i-1]][p] < u - 1) p++;
      if(p < sz(Old) && rev[ar[i-1]][p] == u - 1) New[j] = Old[p];
      maxi = max(maxi, i - New[j] + 1);
    }
    if(maxi >= m) doable[i] = 1;
    swap(Old, New);
  }

  for(int i=1;i<=n;i++) dp[i] = INF;
  dp[0] = 0;
  
  deque<array<int,2>> dq;
  dq.push_back({0, 0});

  for(int i=1;i<=n;i++){
    if(doable[i] == 1){
      while(!dq.empty() &&  i - dq.front()[0] > m) dq.pop_front();
      if(!dq.empty() && dq.front()[1] != INF) dp[i] = dq.front()[1] + 1;
    }
    while(!dq.empty() && dq.back()[1] >= dp[i]) dq.pop_back();
    dq.push_back({i, dp[i]});
  }

  if(dp[n] == INF) return -1;
  else return dp[n];
}

/*void _(){
  int n,m,k;
  cin >> n >> m >> k;

  int ar[n+5];
  for(int i=1;i<=n;i++) cin >> ar[i];

  vector<int> v[2*m+5];
  for(int i=1;i<=m;i++){
  	int u; cin >> u;
  	for(int j = 0; j < u; j++){
  		int val; cin >> val;
  		v[i].push_back(val);
  		v[i+m].push_back(val);
  	}
  }
 
  auto Query = [&](int ind,int val){
     int it = lower_bound(all(v[ind]),val) - v[ind].begin();
     if(it != sz(v[ind]) && v[ind][it] == val) return 1;
     return 0;
  }; 

  int doable[n+5],dp[n+5];
  memset(doable,0,sizeof(doable));

  for(int i=m;i<=n;i++){
    for(int j = 1; j <= m; j++){
      int p = j;
      int r = j + m - 1;
      while(p <= r && Query(p,ar[i-m+1+p-j])) p++;
      if(p > r){
        doable[i] = 1;
        break;
      }
    }
  }

  for(int i=1;i<=n;i++) dp[i] = INF;
  dp[0] = 0;
  
  deque<array<int,2>> dq;
  dq.push_back({0, 0});

  for(int i=1;i<=n;i++){
    if(doable[i] == 1){
      while(!dq.empty() &&  i - dq.front()[0] > m) dq.pop_front();
      if(!dq.empty() && dq.front()[1] != INF) dp[i] = dq.front()[1] + 1;
    }
    while(!dq.empty() && dq.back()[1] >= dp[i]) dq.pop_back();
    dq.push_back({i, dp[i]});
  }

  if(dp[n] == INF) cout << -1 << '\n';
  else cout << dp[n] << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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