Submission #1292091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292091		Hamed_Ghaffari	벽 칠하기 (APIO20_paint)	C++20	100 / 100	141 ms	13304 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

#define maxs(a, b) (a = max(a, b))

const int MXN = 1e5+5;

vector<int> vec[MXN];
int mx[MXN], val[2][MXN];

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    for(int i=0; i<M; i++)
        for(int j=0; j<A[i]; j++)
            vec[B[i][j]].push_back(i);
    for(int i : vec[C[N-1]]) {
        val[(N-1)&1][i] = 1;
        mx[N-1] = 1;
    }
    for(int i=N-2; i>=0; i--) {
        if(i+2<N)
            for(int j : vec[C[i+2]])
                val[i&1][j] = 0;
        for(int j : vec[C[i]])
            maxs(mx[i], val[i&1][j] = val[(i&1)^1][(j+1)%M]+1);
    }
    int ans = 0;
    int av=0;
    int lst=-1;
    while(av<N) {
        ans++;
        bool fnd = 0;
        for(int i=av; i>lst; i--)
            if(mx[i]>=M) {
                fnd = 1;
                lst = av;
                av = i+M;
            }
        if(!fnd) return -1;
    }
    return ans;
}

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