제출 #1203212

#제출 시각아이디문제언어결과실행 시간메모리
1203212O_ElmasryPainting Walls (APIO20_paint)C++20
28 / 100
1601 ms157996 KiB
#include "paint.h" #include<bits/stdc++.h> using namespace std; #include <vector> using ll = long long; const ll INF = 1e9; struct Segment_Tree{ int sz = 1; vector<int>tree; Segment_Tree(int N){ while(sz < N)sz <<= 1; tree.resize(sz * 2, INF); } #define left node * 2 + 1 #define right node * 2 + 2 void update(int idx, int val, int node, int l, int r){ if(l == r)return void(tree[node] = val); int mid = l + r >> 1; if(idx <= mid)update(idx, val, left, l, mid); else update(idx, val, right, mid + 1, r); tree[node] = min(tree[left], tree[right]); } void update(int idx, int val){ update(idx, val, 0, 0, sz - 1); } int query(int lq, int rq, int node, int l, int r){ if(l > rq || r < lq)return INF; if(l >= lq && r <= rq)return tree[node]; int mid = l + r >> 1; return min(query(lq, rq, left, l, mid), query(lq, rq, right, mid + 1, r)); } int query(int lq, int rq){ return query(lq, rq, 0, 0, sz - 1); } #undef left #undef right }; 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; }; Segment_Tree seg(N); for(int i = M - 1;i < N;i++){ bool ok = 0; for(int j = 0;j < M;j++){ ok |= check(j, i - M + 1); if(ok)break; } if(!ok)continue; if(i == M - 1){ dp[i] = 1; } int L = max(0, i - M); ll Min = seg.query(L, i - 1); dp[i] = min(dp[i] , Min + 1); seg.update(i, dp[i]); } return (dp[N - 1] >= INF ? -1 : dp[N - 1]); }
#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...