Submission #367373

#	Time	Username	Problem	Language	Result	Execution time	Memory
367373		jainbot27	Painting Walls (APIO20_paint)	C++17	40 / 100	1600 ms	92652 KiB

paint

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

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

int n, m, k;
vi c, a;
vector<vi> b;
//vector<set<int>> s;
vector<set<int>> al;
vi gud, dp;

map<pii, int> memo;

int solve(int pos, int node){
    if(memo.find({pos, node})!=memo.end()){
        return memo[{pos, node}];
    }
    if(pos>0){
        if(al[c[pos-1]].count((node-1+m)%m)){
            memo[{pos, node}] = 1+solve(pos-1, (node-1+m)%m) ;
        }
        else{
            memo[{pos, node}] = 1;
        }
    }
    else{
        memo[{pos, node}] = 1;
    }
    //cout << pos << ' ' << node << ' ' << memo[{pos, node}] << nl;
    return memo[{pos, node}];
}


int minimumInstructions(int _n, int _m, int _k, vi _c, vi _a, vector<vi> _b){
    n=_n, m=_m, k=_k, c=_c, a=_a, b=_b;
    //s.resize(m);
    al.resize(k);
    F0R(i, m){
        F0R(j, a[i]){
            //s[i].insert(b[i][j]);
            al[b[i][j]].insert(i);
        }
    }
    gud.resize(n);
    dp.resize(n, MOD);
    F0R(i, n){
        trav(x, al[c[i]]){
            if(solve(i, x)>=m){
                gud[i] = 1;
            }
        }
    }
    if(!gud[m-1]){
        return -1;
    }
    else{
        dp[m-1] = 1;
    }
    multiset<int> lst;
    //F0R(i, n) cout << gud[i] << ' ';
    //cout << nl;
    F0R(i, m) lst.insert(dp[i]);
    FOR(i, m, n){
        if(i > m) lst.erase(lst.find(dp[i-m-1]));
        if(gud[i]) dp[i] = *lst.begin()+1;
        lst.insert(dp[i]);
    }
    if(dp[n-1]>=MOD){
        return -1;
    }
    else{
        return dp[n-1];
    }
}

//int32_t main(){
//    ios_base::sync_with_stdio(0); cin.tie(0);
//    int N, M, K;
//    cin >> N >> M >> K;
//    vi C(N);
//    vi A(M); vector<vi> B(M);
//    trav(C2, C) cin >> C2;
//    F0R(i, M){
//        cin >> A[i];
//        B[i].resize(A[i]);
//        F0R(j, A[i]){
//            cin >> B[i][j];
//        }
//    }
//    cout << minimumInstructions(N, M, K, C, A, B) << nl;


//    return 0;
//}

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