Submission #1032277

#TimeUsernameProblemLanguageResultExecution timeMemory
10322770npataPainting Walls (APIO20_paint)C++17
0 / 100
1588 ms348 KiB
#include "paint.h" #include<bits/stdc++.h> using namespace std; #define vec vector int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) { vec<set<int>> b(M); for(int i = 0; i<M; i++) { for(int j = 0; j<B[i].size(); j++) { b[i].insert(B[i][j]); } } vec<int> pref_match(N); vec<int> suf_match(N); for(int i = 0; i<N; i++) { for(int j = 0; j<M; j++) { if(i+j == N) break; if(!b[j].count(C[i+j])) break; pref_match[i]++; } //cerr << pref_match[i] << ' '; } //cerr << '\n'; for(int i = 0; i<N; i++) { for(int j = 0; j<M; j++) { if(i-j == -1) break; if(!b[M-j-1].count(C[i-j])) break; suf_match[i]++; } // cerr << suf_match[i] << ' '; } //cerr << '\n'; int lst = 0; int ans = 0; while(lst != N) { int bst = -1; for(int i = lst; i<min(lst+M, N); i++) { int need = i-lst; if(i > 0 && suf_match[i-1] < need) continue; if((i > 0 ? suf_match[i-1] : 0) + pref_match[i] < M) continue; bst = i+min(pref_match[i], M-need); } if(bst == -1) return -1; lst = bst; ans++; } return ans; }

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   for(int j = 0; j<B[i].size(); j++) {
      |                  ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...