Submission #965720

#	Time	Username	Problem	Language	Result	Execution time	Memory
965720		Pring	벽 칠하기 (APIO20_paint)	C++17	28 / 100	1595 ms	9816 KiB

paint

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

namespace {
    const int MXN = 200005, INF = 1e9;
    int n, m, k;
    vector<int> c;
    vector<vector<int>> clr;

    int cid[MXN], worker[MXN];
    bitset<MXN> b;
    int dp[MXN];

    bool calc(int sr) {
        auto check = [&](int x) -> bool {
            FOR(i, 0, m) {
                auto it = lower_bound(clr[(x + i) % m].begin(), clr[(x + i) % m].end(), c[sr + i]);
                if (it == clr[(x + i) % m].end()) return false;
                if (*it != c[sr + i]) return false;
            }
            return true;
        };
        FOR(x, 0, m) if (check(x)) return true;
        return false;
    }

    int miku() {
        FOR(i, m, n + 1) b[i] = calc(i - m);
        deque<pii> dq;
        dq.push_back(mp(0, 0));
        FOR(i, 1, n + 1) {
            if (!b[i]) dp[i] = INF;
            else {
                while (dq.front().sc < i - m) dq.pop_front();
                dp[i] = dq.front().fs + 1;
            }
            while (dq.size() && dq.back().fs >= dp[i]) dq.pop_back();
            dq.push_back(mp(dp[i], i));
        }
        return (dp[n] >= INF ? -1 : dp[n]);
    }
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    ::n = N;
    ::m = M;
    ::k = K;
    ::c = C;
    ::clr = B;
    return miku();
}

Compilation message (stderr)

paint.cpp:28:19: warning: '{anonymous}::worker' defined but not used [-Wunused-variable]
   28 |     int cid[MXN], worker[MXN];
      |                   ^~~~~~
paint.cpp:28:9: warning: '{anonymous}::cid' defined but not used [-Wunused-variable]
   28 |     int cid[MXN], worker[MXN];
      |         ^~~

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