| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 576612 | 2022-06-13T08:38:07 Z | shayanebrahimi | Painting Walls (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(int 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(int 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(int 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];
}