Submission #303250

#	Time	Username	Problem	Language	Result	Execution time	Memory
303250		nafis_shifat	Painting Walls (APIO20_paint)	C++14	100 / 100	798 ms	15320 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int inf=1e8;
int minimumInstructions(int N, int M, int K,vector<int> C, vector<int> A,vector<vector<int>> B) {
	

	vector<int> cn[K];


    for(int i=0;i<M;i++) {
    	for(auto j:B[i]) cn[j].push_back(i);
    }

    bool isen[N];
    memset(isen,false,sizeof(isen));

    

    int dp[M]={};
    int vis[M]={};

    for(int i: cn[C[0]]) {
    	dp[i]=1;
    	vis[i]=1;
    	if(M==1) isen[i]=1;
    }

   



    for(int j=1;j<N;j++) {

    	vector<pii> cur;

    	for(int i : cn[C[j]]) {

    	    int y=(i-1+M)%M;

    	    int t;
    	    if(vis[y]==j) {
    	    	t=dp[y]+1;
    	    } else {
    	    	t=1;
    	    }

    	    

    	    cur.push_back({i,t});
    	  
    	    if(t>=M) {
    	    	isen[j]=true;    	    	
    	    }

    	}

    	for(pii x: cur) {
    		dp[x.first]=x.second;
    		vis[x.first]=j+1;
    	}


    }
  

    int dp2[N];

    for(int i=0;i<N;i++)dp2[i]=inf;
    if(!isen[M-1]) return -1;
    dp2[M-1]=1;

    int pt=M-1;


    for(int i=M;i<N;i++) {
    	if(!isen[i]) continue;
 
 
    	int  mn=inf;

    	while(pt < i-M) pt++;
    	while(pt < i-1 && dp2[pt]>=inf) pt++;

    	dp2[i]=dp2[pt]+1;
    }
  


    if(dp2[N-1]>=inf) return -1;
    return dp2[N-1];


}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:81:11: warning: unused variable 'mn' [-Wunused-variable]
   81 |      int  mn=inf;
      |           ^~

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