Submission #761165

#	Time	Username	Problem	Language	Result	Execution time	Memory
761165		Andrei	Painting Walls (APIO20_paint)	C++17	100 / 100	574 ms	253020 KiB

paint

#include <bits/stdc++.h>

#include "paint.h"

using namespace std;

vector <vector <int>> likers;

vector <int> pos;

vector <vector <int>> spreadLeft;

deque <int> dq;

vector <int> dp;

/**
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
*/

int minimumInstructions(int N,int M,int K,vector <int> C,vector <int> A,vector <vector <int>> B)
{
    likers.resize(K);
    for(int i=0; i<M; i++)
        for(auto it:B[i])
            likers[it].push_back(i);

    pos.resize(M);
    for(int i=0; i<M; i++)
        pos[i]=-1;

    dp.resize(N);

    spreadLeft.resize(N);

    for(int i=0; i<N; i++)
    {
        spreadLeft[i].resize(likers[C[i]].size());

        int maxim;
        if(i>0)
        {
            maxim=0;
            for(int j=0; j<(int)likers[C[i]].size(); j++)
            {
                int pj=pos[(likers[C[i]][j]-1+M)%M];
                if(pj==-1)
                    spreadLeft[i][j]=1;
                else
                    spreadLeft[i][j]=spreadLeft[i-1][pj]+1;
                maxim=max(maxim,spreadLeft[i][j]);
            }
        }
        else
        {
            maxim=1;
            for(int j=0; j<(int)likers[C[i]].size(); j++)
                spreadLeft[i][j]=1;
        }

        if(i>0)
        {
            for(int j=0; j<(int)likers[C[i-1]].size(); j++)
                pos[likers[C[i-1]][j]]=-1;
        }
        for(int j=0; j<(int)likers[C[i]].size(); j++)
            pos[likers[C[i]][j]]=j;

        if(i<M-1)
            dp[i]=N+1;
        else if(i==M-1)
        {
            if(maxim<M)
                return -1;
            dp[i]=1;
        }
        else
        {
            while(!dq.empty() && dq.front()<i-M)
                dq.pop_front();

            if(maxim>=M)
                dp[i]=min(N+1,dp[dq.front()]+1);
            else
                dp[i]=N+1;
        }
        while(!dq.empty() && dp[dq.back()]>=dp[i])
            dq.pop_back();
        dq.push_back(i);
   }

   if(dp[N-1]==N+1)
        return -1;
   return dp[N-1];
}

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