Submission #717533

#	Time	Username	Problem	Language	Result	Execution time	Memory
717533		alvingogo	Painting Walls (APIO20_paint)	C++14	63 / 100	1574 ms	15916 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int> > b) {
    vector<int> aval(n);
    int mod=m;
    vector<vector<int> > gg(k);
    for(int i=0;i<m;i++){
        for(auto h:b[i]){
            gg[h].push_back(i);
        }
    }
    vector<int> t(m);
    vector<int> x(m);
    for(int i=0;i<n;i++){
        for(auto h:gg[c[i]]){
            int u=((h-i)%mod+mod)%mod;
            t[u]++;
            x[u]=1;
            if(t[u]>=m){
                aval[i]=1;
            }
        }
        if(i){
            for(auto h:gg[c[i-1]]){
                int u=((h-(i-1))%mod+mod)%mod;
                if(!x[u]){
                    t[u]=0;
                }
            }
        }
        for(auto h:gg[c[i]]){
            int u=((h-i)%mod+mod)%mod;
            x[u]=0;
        }
    }
    multiset<int> s;
    s.insert(0);
    vector<int> dp(n);
    for(int i=0;i<m-1;i++){
        dp[i]=1e9;
        s.insert(1e9);
    }
    for(int i=m-1;i<n;i++){
        if(aval[i]){
            dp[i]=(*s.begin())+1;
        }
        else{
            dp[i]=1e9;
        }
        if(i==m-1){
            s.erase(s.find(0));
        }
        else{
            s.erase(s.find(dp[i-m]));
        }
        s.insert(dp[i]);
    }
    if(dp[n-1]>5e8){
        return -1;
    }
    return dp[n-1];
}

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