| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 576601 | 2022-06-13T08:30:25 Z | shayanebrahimi | 벽 칠하기 (APIO20_paint) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define debug(e) cerr << #e << ": " << e << endl;
#define fast_io; ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll MOD=10957;//1e9+7//998244353//1e9+9//1111211111;
//ll tavmd(ll a,ll b){if(b==0){return 1;}if(b%2==0){ll x=tavmd(a,b/2);return(x*x)%MOD;}else{return(a%MOD*tavmd(a,b-1)%mOD)%MOD;}}
const ll MAXN=2e5+10;
const ll INF=3e18;
const ll LOG=30;
vector<ll>vec[MAXN];
set<pair<ll,ll>>st;
bool mark[MAXN];
ll dpv[2][MAXN],dp[MAXN];
ll minimumInstructions(ll n,ll m,ll k,vector<ll>c,vector<ll>a,vector<vector<ll>>b){
for(int i=0;i<m;i++){
for(ll j=0;j<a[i];j++){
vec[b[i][j]].emplace_back(i);
}
}
memset(dp,-1,sizeof(dp));
memset(dpv,-1,sizeof(dpv));
for(auto it:vec[c[n-1]]){
dpv[(n-1)&1][it]=n-1;
if(dpv[(n-1)&1][it]-(n-1)+1>=m){
mark[n-1+m-1]=true;
}
}
for(int i=n-2;i>=0;i--){
for(auto it:vec[c[i]]){
if(dpv[(i+1)&1][(it+1)%m]==-1){
dpv[i&1][it]=i;
}
else{
dpv[i&1][it]=dpv[(i+1)&1][(it+1)%m];
}
if(dpv[i&1][it]-i+1>=m){
mark[i+m-1]=true;
}
}
for(auto it:vec[c[i+1]]){
dpv[(i+1)&1][it]=-1;
}
}
dp[0]=0;
st.emplace(0,0);
for(int i=m;i<=n;i++){
if(mark[i-1]&&!st.empty()){
dp[i]=1+(*st.begin()).first;
st.emplace(dp[i],i);
}
if(dp[i-m]!=-1){
st.erase(st.lower_bound({dp[i-m],i-m}));
}
}
return dp[n];
}