Submission #1225939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225939		KALARRY	Painting Walls (APIO20_paint)	C++20	100 / 100	488 ms	265296 KiB

paint

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int n,m,dp[100005],c[100005],is_end[100005];
map<int,int> my_ord[100005];
map<int,bool> likes[100005];
vector<int> f[100005];
vector<int> max_ends[100005];

void calc()
{
    for(int i = 1 ; i <= n ; i++)
    {
        max_ends[i] = f[c[i]];
        for(int j = 0 ; j < max_ends[i].size() ; j++)
            max_ends[i][j] = 1;
        if(m==1 && f[c[i]].size() > 0)
            is_end[i] = true;
    }
    for(int i = 2 ; i <= n ; i++)
    {
        for(int j = 0 ; j < max_ends[i].size() ; j++)
        {
            int x = f[c[i]][j];
            int prev = x-1;
            if(x==0)
                prev = m-1;
            if(!likes[prev][c[i-1]])
                continue;
            int check = max_ends[i-1][my_ord[prev][c[i-1]]];
            max_ends[i][j] = min(m,check + 1);
            if(max_ends[i][j]==m)
                is_end[i] = true;
        }
    }
}

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) 
{
    n = N;
    m = M;
    for(int i = N ; i >= 1 ; i--) //make it 1-indexed
        c[i] = C[i-1];
    for(int j = 0 ; j < M ; j++)
        for(int s = 0 ; s < A[j] ; s++)
        {
            int x = B[j][s];
            likes[j][x] = true;
            f[x].push_back(j);
            my_ord[j][x] = f[x].size() - 1;
        }
    calc();
    dp[0] = 0;
    deque<int> avail;
    avail.push_back(0);
    for(int i = 1 ; i <= N ; i++)
    {
        dp[i] = -1;
        if(avail.empty())
            continue;
        if(i >= M+1 && avail.front() == dp[i-M-1])
            avail.pop_front();
        if(!is_end[i])
            continue;
        dp[i] = avail.front() + 1;
        while(avail.back() > dp[i])
            avail.pop_back();
        avail.push_back(dp[i]);
    }
    return dp[N];
}

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