Submission #1154360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154360		ace5	Painting Walls (APIO20_paint)	C++20	100 / 100	481 ms	253196 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B)
{
    vector<vector<int>> likes(K);
    for(int j = 0;j < B.size();++j)
    {
        for(int k = 0;k < B[j].size();++k)
        {
            likes[B[j][k]].push_back(j);
        }
    }
    vector<int> p(M,-1);
    vector<vector<int>> dp(N);
    vector<int> mdp(N,0);
    for(int i = N-1;i >= 0;--i)
    {
        dp[i].resize(likes[C[i]].size());
        for(int j = 0;j < likes[C[i]].size();++j)
        {
            int cp = likes[C[i]][j];
            dp[i][j] = (p[(cp+1)%M] == -1 ? 1 : p[(cp+1)%M]+1);
            mdp[i] = max(mdp[i],dp[i][j]);
        }
        if(i != N-1)
        {
            for(int j = 0;j < likes[C[i+1]].size();++j)
            {
                p[likes[C[i+1]][j]] = -1;
            }
        }
        for(int j = 0;j < likes[C[i]].size();++j)
        {
            p[likes[C[i]][j]] = dp[i][j];
        }
    }
    vector<int> ans(N+1,N+2);
    ans[N] = 0;
    multiset<int> bm;
    bm.insert(0);
    for(int i = N-1;i >= 0;--i)
    {
        if(mdp[i] >= M)
        {
            ans[i] = *bm.begin() + 1;
        }
        if(i + M <= N)
        {
            bm.erase(bm.find(ans[i+M]));
        }
        bm.insert(ans[i]);
    }
    return (ans[0] >= N+2 ? -1 : ans[0]);
}

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