Submission #1193488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193488		omsincoconut	Painting Walls (APIO20_paint)	C++17	63 / 100	1599 ms	108012 KiB

paint

/*
We just need to check for each length K segment whether there exist a way to color them or not.
*/

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")

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

using namespace std;

const int INF = (int)1e9;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    vector<int> color_contractor[K];
    for (int i = 0; i < M; i++) {
        for (int j : B[i]) {
            color_contractor[j].push_back(i);
        }
    }

    vector<int> cell[M];

    for (int i = 0; i < N; i++) {
        for (int j : color_contractor[C[i]]) {
            cell[((j-i)%M+M)%M].push_back(i+1);
        }
    }

    int dp[N+1];
    fill(dp, dp+N+1, INF);
    dp[0] = 0;
    deque<pair<int, int>> dt;
    for (int i = 0; i <= N; i++) {
        while (!dt.empty() && i-dt.front().first > M) dt.pop_front();
        if (!dt.empty()) dp[i] = dt.front().second+1;
        if (i+M > N) continue;

        bool can = false;
        for (int j : color_contractor[C[i]]) {
            int c = ((j-i)%M+M)%M;
            can |= (upper_bound(cell[c].begin(), cell[c].end(), i+M) - upper_bound(cell[c].begin(), cell[c].end(), i) == M);
        }
        if (can) {
            while (!dt.empty() && dt.back().second >= dp[i]) dt.pop_back();
            dt.emplace_back(i, dp[i]);
        }
    }

    return (dp[N] >= INF ? -1 : dp[N]);
}

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