Submission #306807

#	Time	Username	Problem	Language	Result	Execution time	Memory
306807		quocnguyen1012	Painting Walls (APIO20_paint)	C++14	100 / 100	852 ms	16400 KiB

paint

#ifndef LOCAL
#include "paint.h"
#endif // LOCAl
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

vector<int> like[maxn];
int sum[maxn], check[maxn];

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
  for(int i = 0; i < M; ++i){
    for(int j : B[i]){
      like[j].pb(i);
    }
  }
  vector<ii> op(M);
  for(int i = 0; i < M; ++i){
    op[i] = mp(-1e9, 0);
  }
  function<int(int, int)> ins = [&](int i, int time)
  {
    if(op[i].fi + 1 == time) op[i] = mp(time, op[i].se + 1);
    else op[i] = mp(time, 1);
    if(op[i].se >= M) return 1;
    else return 0;
  };
  vector<int> f(N + 1);
  priority_queue<ii, vector<ii>, greater<ii>> pq;
  for(int i = 0; i < N; ++i){
    pq.push(mp(f[i], i));
    f[i + 1] = 1e9;
    bool good = false;
    for(int j : like[C[i]]){
      int shift = (i - j + M - 1) % M;
      good |= ins(shift, i);
    }
    if(good){
      while(pq.size() && pq.top().se < i + 1 - M) pq.pop();
      f[i + 1] = pq.top().fi + 1;
    }
  }
  if(f[N] > N) return -1;
  return f[N];
}

#ifdef LOCAL
signed main(void){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int N, M, K; cin >> N >> M >> K;
  vector<int> C(N);
  for(int i = 0; i < N; ++i){
    cin >> C[i];
  }
  vector<int> A(M);
  vector<vector<int>> B(M);
  for(int i = 0; i < M; ++i){
    cin >> A[i];
    B[i].resize(A[i]);
  }
  for(int i = 0; i < M; ++i){
    for(auto & it : B[i]){
      cin >> it;
    }
  }
  cout << minimumInstructions(N, M, K, C, A, B);
}
#endif

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