Submission #1175975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175975		12345678	Painting Walls (APIO20_paint)	C++20	28 / 100	17 ms	6984 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=5e2+5, mx=2e2+5, kx=1e5+5;

int dp[nx][mx], s[nx], mn[nx];
vector<int> g[kx];

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    for (int i=0; i<M; i++) for (auto x:B[i]) g[x].push_back(i);
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<M; j++) dp[i][j]=i+1;
        for (auto idx:g[C[i]]) 
        {
            if (i==0) dp[i][idx]=i;
            else dp[i][idx]=max(i-M+1, dp[i-1][(idx-1+M)%M]);
        }
        mn[i]=1e9;
        for (int j=0; j<M; j++) mn[i]=min(mn[i], dp[i][j]);
        //cout<<"here "<<i<<' '<<mn[i]<<'\n';
    }
    int cur=-1, lst=-2, ans=0;
    while (cur!=N-1)
    {
        int f=0;
        //cout<<"loop "<<cur<<' '<<lst<<'\n';
        for (int i=cur; i>lst; i--) 
        {
            if (mn[i+M]==i+1)
            {
                f=1;
                lst=i;
                ans++;
                cur=i+M;
                break;
            }
        }
        if (!f) return -1;
    }
    return ans;
}

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