Submission #296093

#	Time	Username	Problem	Language	Result	Execution time	Memory
296093		Alexa2001	Painting Walls (APIO20_paint)	C++17	100 / 100	1079 ms	12984 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;

    deque<int> dq;

    dq.push_back(m-1);
    dp[m-1] = 1;

    for(i=m; i<n; ++i)
    {
        if(!ok[i]) continue;

        while(dq.size() && dq.front() < i-m) dq.pop_front();
        if(dq.empty()) return -1;

        dp[i] = dp[dq.front()] + 1;

        dq.push_back(i);
    }

    return dp[n-1];
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:26:12: warning: unused variable 'j' [-Wunused-variable]
   26 |     int i, j;
      |            ^

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