Submission #738499

#	Time	Username	Problem	Language	Result	Execution time	Memory
738499		Abrar_Al_Samit	Painting Walls (APIO20_paint)	C++17	100 / 100	1297 ms	409376 KiB

paint

    #include "paint.h"
    #include <bits/stdc++.h>
    using namespace std;
     
    const int nax = 1e5 + 1;
     
     
    vector<int> col_to_wall[nax], cand[nax];
    bool good[nax];
    int dp[2][700];
     
    int minimumInstructions(
        int N, int M, int K, vector<int> C,
        vector<int> A, vector<vector<int>> B) {
     
        
        for(int i=0; i<N; ++i) {
            col_to_wall[C[i]].push_back(i);
        }
     
        for(int i=0; i<M; ++i) {
            for(int j=0; j<A[i]; ++j) {
                for(int x : col_to_wall[B[i][j]]) {
                    cand[x].push_back(i);
                }
            }
        }
        for(int i=0; i<K; ++i) {
            col_to_wall[i].clear();
        }
     
        int rw = 0;
        for(int i=N-1; i>=1; --i, rw = 1-rw) {
            if(cand[i].empty()) {
                memset(dp[rw], 0, sizeof dp[rw]);
                continue;
            }
     
            int ptr = 0;
            int sz2 = cand[i].size();
            for(int j=0, sz=cand[i-1].size(); j<sz; ++j) {
                dp[rw][j] = 0;
     
                if(cand[i-1][j]+1==M) {
                    if(cand[i][0]==0) {
                        dp[rw][j] = 1 + dp[1-rw][0];
                    }
                    if(i-1<=N-M) {
                        if(dp[rw][j]+1>=M) good[i-1] = 1;
                    }   
                    continue;
                }
     
                while(ptr+1<sz2 && cand[i][ptr+1]<=cand[i-1][j]+1) {
                    ++ptr;
                }
                if(cand[i][ptr]==cand[i-1][j]+1) {
                    dp[rw][j] = 1 + dp[1-rw][ptr];
                }
     
                if(i-1<=N-M) {
                    if(dp[rw][j]+1>=M) good[i-1] = 1;
                }
            }
        }
        if(M==1 && !cand[N-1].empty()) good[N-1] = 1;
     
        if(!good[0]) return -1;
        int last = 0, pending = -1;
     
        int ans = 1;
        for(int i=1; i<N; ++i) {
            if(good[i]) {
                pending = i;
            }
            if(last+M==i) {
                if(pending==-1) return -1;
                last = pending;
                pending = -1;
                ++ans;
            }
        }
        return ans;
    }

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