Submission #1200616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200616		Mohamed_Kachef06	Painting Walls (APIO20_paint)	C++17	28 / 100	1596 ms	6472 KiB

paint

#include "paint.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin() , x.end()
const int N = 1e5 , K = 1e5; 

bool valid[N+1]; 
int dp[N+1]; 
vector<int> f[K+1]; 

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
   for (int i = 0 ; i < M ; i++){
     for (auto j : B[i]) f[j].push_back(i); 
   }

    for (int x = 0 ; x < M ; x++){
      for (int y = 0 ; y <= N - M ; y++){
        bool v = 1;
          for (int l = 0 ; l < M ; l++){
            int cons = (x + l)%M , cell = C[y + l]; 
            v&= binary_search(all(f[cell]) , cons); 
          }
          valid[y]|=v; 
      }
    }
    for (int i = 1 ; i <= N ; i++) dp[i] = 2e9; 
    multiset<int> st; 
    if (valid[0]) st.insert(0); 
    for (int i = 1 ; i <= N ; i++){
      if (!st.empty()) dp[i] = *st.begin() + 1; 
      if (valid[i]) st.insert(dp[i]); 
      if (i >= M && valid[i-M]) st.erase(st.find(dp[i-M])) ;
    }
    return (dp[N] >= 2e9 ? -1 : dp[N]); 
}


// dp[i] = min(dp[j]) for all j >= i - m and there 

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