Submission #296092

#	Time	Username	Problem	Language	Result	Execution time	Memory
296092		Alexa2001	Painting Walls (APIO20_paint)	C++17	100 / 100	1085 ms	14720 KiB

paint

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

using namespace std;

const int Nmax = 1e5 + 5;

vector<int> good[Nmax];

int nr = 0, n, m;
int shift[Nmax];
bool ok[Nmax];
int dp[Nmax];


void upd(int pos, int add)
{
    nr -= (shift[pos] == m);
    shift[pos] += add;
    nr += (shift[pos] == m);
}

int minimumInstructions(int N, int M, int k, vector<int> c, vector<int> A, vector<vector<int>> B)
{
    n = N; m = M;
    int i, j;
    for(i=0; i<m; ++i)
        for(auto it : B[i])
            good[it].push_back(i);

    for(i=0; i<m; ++i)
        for(auto it : good[c[i]])
            upd((it - i%m + m) % m, +1);

    if(nr) ok[m-1] = 1;

    for(i=m; i<n; ++i)
    {
        for(auto it : good[c[i]])
            upd((it - i%m + m) % m, +1);

        for(auto it : good[c[i-m]])
            upd((it - i%m + m) % m, -1);

        if(nr) ok[i] = 1;
    }

    if(!ok[m-1] || !ok[n-1]) return -1;

    dp[m-1] = 1;
    for(i=m; i<n; ++i)
    {
        for(j=i-m; j<i; ++j)
            if(ok[j])
            {
                dp[i] = dp[j] + 1;
                break;
            }

        if(!dp[i]) 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