Submission #1203159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203159		O_Elmasry	Painting Walls (APIO20_paint)	C++20	28 / 100	1601 ms	157508 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#include <vector>
using ll = long long;
const ll INF = 1e5;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
  vector<ll>dp(N, INF);
  vector<vector<int>>comp(M, vector<int>(N));
  for(int i = 0;i < M;i++){
    sort(B[i].begin(), B[i].end());
  }
  for(int i = 0;i < M;i++){
    for(int j = 0;j < N;j++){
      if(binary_search(B[i].begin(), B[i].end(), C[j]))comp[i][j] = 1;
    }
  }
  auto check = [&](int x, int y){
    bool ok = 1;
    for(int i = 0;i < M;i++){
      int xx = (x + i) % M;
      int yy = y + i;
      ok &= comp[xx][yy];
    }
    return ok;
  };
  for(int i = M - 1;i < N;i++){
    for(int j = 0;j < M;j++){
      bool ok = check(j, i - M + 1);
      if(!ok)continue;
      if(i == M - 1){
        dp[i] = 1;
      }
      for(int k = max(0, i - M);k < i;k++){
        dp[i] = min(dp[i], dp[k] + 1);
        // cout << i << " " << k << " " << j << " " << dp[i] << endl;
      }
    }
  }
  return (dp[N - 1] >= INF ? -1 : dp[N - 1]);
}

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