Submission #1198923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198923		browntoad	Painting Walls (APIO20_paint)	C++20	100 / 100	592 ms	12872 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

namespace{
    const ll maxn = 1e5+5;
    const ll mod = 1e9+7;
    const ll inf = 1ll<<60;
}

int minimumInstructions( int n, int m, int k, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    vector<pii> dp; // current dp, {pos, val}
    vector<int> cols[k];
    REP(i, m){
        for (auto c:B[i]) cols[c].pb(i);
    }

    vector<int> starts;
    RREP(i, n){
        int ptr = 0;
        vector<pii> tdp;
        for (auto id:cols[C[i]]) tdp.pb({id, 1});

        int mx = 0;
        REP(j, SZ(tdp)){
            mx = max(mx, 1);
            while(ptr < SZ(dp) && dp[ptr].f <= tdp[j].f){
                ptr++;
            }
            if (ptr < SZ(dp) && dp[ptr].f == tdp[j].f+1){
                tdp[j].s = dp[ptr].s+1;
                mx = max(mx, tdp[j].s);
            }
            if (tdp[j].f == m-1 && SZ(dp) && dp[0].f == 0){ // special case
                tdp[j].s = dp[0].s+1;
                mx = max(mx, tdp[j].s);
            }
        }
        if (mx >= m){
            starts.pb(i);
        }
        dp = tdp;
    }

    reverse(ALL(starts));
    int r = -1, pos = 0, ans = 0;
    REP(i, n){
        if (r >= i) continue;
        ans++;
        while(pos < SZ(starts) && starts[pos] <= i){
            r = starts[pos]+m-1;
            pos++;
        } 
        if (r < i) return -1;
    }
    return ans;
}

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