Submission #576620

#	Time	Username	Problem	Language	Result	Execution time	Memory
576620		shayanebrahimi	Painting Walls (APIO20_paint)	C++14	100 / 100	481 ms	16404 KiB

paint

#include <bits/stdc++.h>
using namespace std;
typedef int 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=1e5+10;
//const ll INF=3e18;
//const ll LOG=30;
vector<ll>vec[MAXN];
set<pair<ll,ll>>st;
ll 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(int 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];
}

Compilation message (stderr)

paint.cpp:6:9: warning: ISO C++11 requires whitespace after the macro name
    6 | #define fast_io;                 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
      |         ^~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37