Submission #395215

#	Time	Username	Problem	Language	Result	Execution time	Memory
395215		abc864197532	Painting Walls (APIO20_paint)	C++17	63 / 100	1607 ms	407064 KiB

paint

#include <bits/stdc++.h>
// #include "grader_paint.cpp"
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}

int minimumInstructions(int n, int m, int k,vector <int> c, vector <int> a, vector <vector <int>> b) {
    vector <int> tmp[n], pos[k];
    for (int i = 0; i < n; ++i) pos[c[i]].pb(i);
    for (int i = 0; i < m; ++i) {
        for (int j : b[i]) {
            for (int ii : pos[j]) {
                tmp[ii].pb(((i - ii) % m + m) % m);
            }
        }
    }
    vector <int> cnt(m, 0), num(m + 1, 0);
    num[0] = m;
    auto add = [&](int v, int c) {
        num[cnt[v]]--;
        cnt[v] += c;
        num[cnt[v]]++;
    };
    vector <bool> seg(n + 1, false);
    for (int i = 0; i < m; ++i) {
        for (int j : tmp[i]) add(j, 1);
    }
    if (num[m] > 0) seg[m] = true;
    for (int i = m; i < n; ++i) {
        for (int j : tmp[i - m]) add(j, -1);
        for (int j : tmp[i]) add(j, 1);
        if (num[m] > 0) seg[i + 1] = true;
    }
    vector <int> dp(n + 1, 1 << 30);
    dp[0] = 0;
    deque <int> dq = {0};
    for (int i = 1; i <= n; ++i) if (seg[i]) {
        while (!dq.empty() && dq.front() < i - m) dq.pop_front();
        if (!dq.empty()) dp[i] = dp[dq.front()] + 1;
        while (!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
        dq.push_back(i);
    }
    if (dp[n] > n) dp[n] = -1;
    return dp[n];
}

/*
 8 3 5
 3 3 1 3 4 4 2 2
 3 0 1 2
 2 2 3
 2 3 4

 5 4 4
 1 0 1 2 2
 2 0 1
 1 1
 1 2
 1 3
 */

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