Submission #576026

#	Time	Username	Problem	Language	Result	Execution time	Memory
576026		handlename	Painting Walls (APIO20_paint)	C++17	100 / 100	685 ms	14900 KiB

paint

#include <bits/stdc++.h>
//#include "paint.h"
using namespace std;
#define pb push_back
#define mp make_pair
vector<int> adj[100001];
bool works[100001];
int dp[100001],curtot;
deque<int> num; //numi starts with i
int minimumInstructions(int n,int m,int k,vector<int> arr,vector<int> A,vector<vector<int> > B){
    for (int i=0;i<m;i++){
        for (int j=0;j<A[i];j++){
            adj[B[i][j]].pb(i);
        }
        num.pb(0);
    }
    for (int i=0;i<m;i++){
        for (auto j:adj[arr[i]]){
            num[(j-i+m)%m]++;
        }
    }
    for (int i=0;i<m;i++){
        if (num[i]==m) curtot++;
    }
    if (curtot>0) works[0]=true;
    for (int i=0;i<n-m;i++){
        for (auto j:adj[arr[i]]){
            if (num[j]==m) curtot--;
            num[j]--;
        }
        for (auto j:adj[arr[i+m]]){
            num[j]++;
            if (num[j]==m) curtot++;
        }
        num.push_front(num.back());
        num.pop_back();
        if (curtot>0) works[i+1]=true;
        //if (works[i]) cout<<i<<'\n';
    }
    for (int i=1;i<=n;i++){
        dp[i]=1e9;
    }
    deque<pair<int,int> > dq;
    dq.pb(mp(0,0));
    for (int i=m;i<=n;i++){
        if (!works[i-m]) continue;
        while (!dq.empty() && dq[0].second<i-m){
            dq.pop_front();
        }
        if (dq.empty()) return -1;
        dp[i]=dq[0].first+1;
        while (!dq.empty() && dq.back().first>=dp[i]){
            dq.pop_back();
        }
        dq.pb(mp(dp[i],i));
    }
    if (dp[n]==1e9) return -1;
    return dp[n];
}

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