Submission #568245

#	Time	Username	Problem	Language	Result	Execution time	Memory
568245		hibiki	Painting Walls (APIO20_paint)	C++11	100 / 100	729 ms	13880 KiB

paint

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

#define pb push_back
#define f first
#define s second

int n,m,k;
int dp[100100];
queue<int> q;
vector<int> v[100100];
int train_p[100100],train_n[100100];

int minimumInstructions(
    int N, int M, int K, vector<int> C,
    vector<int> A, vector<vector<int>> B)
{
    n = N, m = M, k = K;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < A[i]; j++)
            v[B[i][j]].pb(i);
    dp[n] = 0;
    q.push(n);
    for(int i = n - 1; i >= 0; i--)
    {
        bool fi = false;
        // for(auto val:temp)
        //     printf("%d %d\n",val.f,val.s);
        // printf("---\n");
        while(q.size() && q.front() > i + m)q.pop();
        if(q.empty())return -1;
        for(int val: v[C[i]])
        {
            train_n[val] = train_p[(val + 1) % m] + 1;
            if(train_n[val] >= m)
                fi = true;
        }
        if(i != n - 1)
            for(int val: v[C[i + 1]])
                train_p[val] = 0;
        for(int val: v[C[i]])
            train_p[val] = train_n[val];
        if(fi)
        {
            dp[i] = dp[q.front()] + 1;
            q.push(i);
        }
    }
    if(dp[0] == 0) return -1;
    return dp[0];
}

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