Submission #348623

#	Time	Username	Problem	Language	Result	Execution time	Memory
348623		denkendoemeer	Painting Walls (APIO20_paint)	C++14	100 / 100	556 ms	14956 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
int dp[2][50005],viz[100005];
vector<int>g[100005];
int minimumInstructions(int n,int m,int k,vector<int>c,vector<int>a,vector<vector<int>>b)
{
    int i;
    for(i=0;i<m;i++)
        for(auto it:b[i])
            g[it].push_back(i);
    for(i=n-1;i>=0;i--){
        for(auto it:g[c[i+2]])
            dp[i%2][it]=0;
        for(auto it:g[c[i]]){
            dp[i%2][it]=dp[(i+1)%2][(it+1)%m]+1;
            if (dp[i%2][it]>=m)
                viz[i]=1;
        }
    }
    int ans=0,last=-1,maxi=-m;
    for(i=0;i<n;i++){
        if (viz[i])
            maxi=i;
        if (i>last){
            if (maxi+m==i)
                return -1;
            ans++;
            last=maxi+m-1;
        }
    }
    return ans;
}

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