| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1358552 | KasymK | 벽 칠하기 (APIO20_paint) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
#include "paint.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
#define mm make_pair
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int nx=1e5+5, mx=5e4+5, kx=1e5+5;
int dp[mx], mn[nx];
vector<int> g[kx];
vector<pii> pv;
int minimumInstructions(int N, int M, int K,vector<int> C,vector<int> A,vectorvector<int>> B) {
for(int i = 0; i < M; ++i)
for(auto x : B[i])
g[x].pb(i);
for(int i = 0; i < M; ++i)
dp[i]=1e9;
for(int i=0; i<N; ++i){
vector<pii> nw;
mn[i]=1e9;
for(auto idx:g[C[i]]) {
if(dp[(idx-1+M)%M]==1e9)
nw.pb({idx, i}), umin(mn[i], i);
else
nw.pb({idx, dp[(idx-1+M)%M]}), umin(mn[i], dp[(idx-1+M)%M]);
}
for(auto [idx, x]:pv)
dp[idx]=1e9;
for(auto [idx, x]:nw)
dp[idx]=x;
pv=nw;
}
int l=M-1, r=M-1, answer=0;
while(l<N){
for(int i = r; i >= l; i--){
if(mn[i]<=i-M+1){
l=i+1, r=i+M, answer++;
break;
}
if(i==l)
return -1;
}
}
return answer;
}